Submission #113199

#TimeUsernameProblemLanguageResultExecution timeMemory
113199ansol4328Bali Sculptures (APIO15_sculpture)C++11
100 / 100
91 ms768 KiB
#include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; int n, a, b; ll m[2005], s[2005]; int dp[2005][2005]; const int INF=1e9; int main() { scanf("%d %d %d",&n,&a,&b); for(int i=1 ; i<=n ; i++) { scanf("%lld",&m[i]); s[i]=s[i-1]+m[i]; } ll res=1, idx=1; while(res<s[n]) idx<<=1, (res<<=1)+=1; if(a==1) { while(idx!=0) { for(int i=1 ; i<=n ; i++) dp[1][i]=INF; (res&=~idx); for(int i=1 ; i<=n ; i++) { for(int j=i-1 ; j>=0 ; j--) { if((res|(s[i]-s[j]))==res) dp[1][i]=min(dp[1][i],dp[1][j]+1); } } if(dp[1][n]>b) res|=idx; idx>>=1; } } else { while(idx!=0) { bool tf=false; (res&=~idx); for(int i=1 ; i<=n ; i++) { dp[1][i]=INF; if((s[i]|res)==res) dp[1][i]=1; } for(int k=2 ; k<=b ; k++) { for(int i=k ; i<=n ; i++) { dp[k][i]=INF; for(int j=i-1 ; j>=k-1 ; j--) { if((res|(s[i]-s[j]))==res && dp[k-1][j]==k-1) dp[k][i]=k; } } if(k>=a && dp[k][n]!=INF) { tf=true; break; } } if(!tf) res|=idx; idx>>=1; } } printf("%lld",res); return 0; }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&n,&a,&b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sculpture.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&m[i]);
         ~~~~~^~~~~~~~~~~~~~
#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...