# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
44717178 |
Practice:
_Anas__ |
1025D
- 48
|
C++14 (GCC 6-32)
|
Accepted
|
249 ms
|
1456 KB
|
2018-10-23 02:04:24 |
2018-10-23 02:04:24 |
|
#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;
}
Click to see test details