Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

|

General

# Author Problem Lang Verdict Time Memory Sent Judged
44717178 Practice:
Roohi
1025D - 48 GNU C++14 Accepted 249 ms 1456 KB 2018-10-23 02:04:24 2018-10-23 02:04:24

→ Source
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;
typedef vector<int> vec;

#define ones(x) __builtin_popcount(x)
#define onesl(x) __builtin_popcountl(x)
#define onesll(x) __builtin_popcountll(x)

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define scn(n) scanf("%d",&n)
#define scnll(n) scanf("%lld",&n)
#define scn2(n,m) scanf("%d%d",&n,&m)
#define scn3(n,m,w) scanf("%d%d%d",&n,&m,&w)
#define scn2ll(n,m) scanf("%lld%lld",&n,&m)
#define atoz(v) v.begin(),v.end()
#define ratoz(v) v.rbegin(),v.rend()
#define Fill(a,v) memset(a,v,sizeof(a))
#define sz(v) v.size()
#define fi first
#define se second
#define inf 1e9
#define pi acos(-1.0)
#define sqr(x) x*x
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define ten(n) (int)1e##n
#define tenll(n) (lli)1e##n

int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

/**
ordered_set X;

X.insert(1);
X.insert(2);
X.insert(4);
X.insert(8);
X.insert(16);

cout<<*X.find_by_order(1)<<endl; // 2
cout<<*X.find_by_order(2)<<endl; // 4
cout<<*X.find_by_order(4)<<endl; // 16
cout<<(end(X)==X.find_by_order(6))<<endl; // true

cout<<X.order_of_key(-5)<<endl;  // 0
cout<<X.order_of_key(1)<<endl;   // 0
cout<<X.order_of_key(3)<<endl;   // 2
cout<<X.order_of_key(4)<<endl;   // 2
cout<<X.order_of_key(400)<<endl; // 5
*/

#define N 701

bool dp[N][N][2] , edge[N][N];

int main()
{
///freopen("output.txt","w",stdout);
///freopen("input.txt","r",stdin);
/*
ios_base::sync_with_stdio(false);
cin.tie(0);
*/

int n;
scn(n);
int a[n];

for(int i=0; i<n; i++) scn(a[i]);

for(int i=0; i<n; i++){

dp[i][i][0] = dp[i][i][1] = 1;

for(int j=0; j<n; j++) edge[i][j] = (__gcd(a[i],a[j]) > 1);
}

for(int len=1; len<=n; len++){

for(int left = 0 ; (left+len-1) < n ; left++){

int right = left+len-1;

for(int root = left; root<=right ; root++){

dp[left][right][0] |= (dp[left+1][root][1] && dp[root][right][0] && edge[left][root]);

dp[left][right][1] |= (dp[left][root][1] && dp[root][right-1][0] && edge[right][root]);
}
}
}

cout<<((dp[0][n-1][0] || dp[0][n-1][1])?"Yes" : "No");

return 0;
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?