Submission #1076054

#TimeUsernameProblemLanguageResultExecution timeMemory
1076054alexddBali Sculptures (APIO15_sculpture)C++17
100 / 100
96 ms600 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n,a,b; int y[2005],sump[2005]; bool verif(int lim) { vector<vector<bool>> dp(n+2,vector<bool>(b+2,0)); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int cnt=1;cnt<=b;cnt++) { dp[i][cnt]=0; for(int j=0;j<i;j++) { if(dp[j][cnt-1] && (lim|(sump[i]-sump[j]))==lim) dp[i][cnt]=1; } } } for(int i=a;i<=b;i++) if(dp[n][i]) return 1; return 0; } bool verif1(int lim) { vector<int> dp(n+2); dp[0]=0; for(int i=1;i<=n;i++) { dp[i]=b+1; for(int j=0;j<i;j++) { if((lim|(sump[i]-sump[j]))==lim) dp[i] = min(dp[i], dp[j]+1); } } if(dp[n]<=b) return 1; else return 0; } /** dp[i][cnt] = 0/1 dp[i][cnt] |= dp[x][cnt-1], daca */ signed main() { cin>>n>>a>>b; for(int i=1;i<=n;i++) { cin>>y[i]; sump[i] = sump[i-1]+y[i]; } if(a==1) { int pref=(1LL<<60)-1; for(int b=59;b>=0;b--) { pref -= (1LL<<b); if(!verif1(pref)) pref += (1LL<<b); } cout<<pref; } else { int pref=(1LL<<60)-1; for(int b=59;b>=0;b--) { pref -= (1LL<<b); if(!verif(pref)) pref += (1LL<<b); } cout<<pref; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...