Submission #76821

#TimeUsernameProblemLanguageResultExecution timeMemory
76821vexBali Sculptures (APIO15_sculpture)C++14
100 / 100
364 ms876 KiB
#include <bits/stdc++.h> #define maxn 2005 using namespace std; int n,a,b; long long s[maxn]; bool moze(int x) { int g=0; int pr=0; long long tr=1LL<<x; for(int i=1;i<=n;i++) { if(s[i]-s[pr]>=tr) { if(i==pr+1)return false; g++; pr=i-1; i--; } else if(i==n)g++; } if(g<=b)return true; return false; } int numbit() { int l=0; int r=50; int sol; while(l<=r) { int mid=(l+r)/2; if(moze(mid)) { sol=mid; r=mid-1; } else l=mid+1; } return sol; } bool t[maxn][maxn]; bool exist(long long br0,int numb) { long long br=1LL<<numb; for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)t[i][j]=false; t[0][0]=true; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) { if(((s[i]-s[j])&br0)==0LL && (s[i]-s[j])<br) { for(int k=0;k<=n-1;k++)if(t[j][k])t[i][k+1]=true; } } for(int i=a;i<=b;i++)if(t[n][i])return true; return false; } int dp2[maxn]; bool exist2(long long br0,int numb) { long long br=1LL<<numb; for(int i=1;i<=n;i++)dp2[i]=b+1; dp2[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) { if(((s[i]-s[j])&br0)==0LL && (s[i]-s[j])<br && dp2[j]+1<dp2[i]) { dp2[i]=dp2[j]+1; } } return dp2[n]<=b; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n>>a>>b;s[0]=0LL; for(int i=1;i<=n;i++) { int x; cin>>x; s[i]=s[i-1]+x; } int br=numbit(); if(br==0) { cout<<0<<endl; return 0; } long long sol=1LL<<(br-1); long long obr=0; if(a==1) { for(int i=br-2;i>=0;i--) { obr+=1LL<<i; if(!exist2(obr,br)) { obr-=1LL<<i; sol+=1LL<<i; } } cout<<sol<<endl; return 0; } for(int i=br-2;i>=0;i--) { obr+=1LL<<i; if(!exist(obr,br)) { obr-=1LL<<i; sol+=1LL<<i; } } cout<<sol<<endl; return 0; } /* 6 1 3 8 1 2 1 5 4 */

Compilation message (stderr)

sculpture.cpp: In function 'int numbit()':
sculpture.cpp:42:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return sol;
            ^~~
#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...