Submission #409444

#TimeUsernameProblemLanguageResultExecution timeMemory
409444TLP39Bali Sculptures (APIO15_sculpture)C++14
50 / 100
186 ms4420 KiB
#include <stdio.h> #include <math.h> #include <utility> #include <string.h> #include <iostream> #include <vector> #include <algorithm> #include <queue> #include <map> using namespace std; typedef long long int ll; typedef pair<int,int> pp; int n,a,b; ll y[2001]; ll qs[2001]={}; bool cango[2001][2001]; int dist[2001]; ll tot=0; void init() { scanf("%d %d %d",&n,&a,&b); qs[0]=0; for(int i=1;i<=n;i++) { scanf("%lld",&y[i]); qs[i]=qs[i-1]+y[i]; } for(int i=0;i<n;i++) { for(int j=i+1;j<=n;j++) { cango[i][j]=true; } } } bool checkgo(int p,int q,int r) { return ((qs[q]-qs[p])>>r)&1; } bool testgo(int r) { dist[0]=0; for(int i=1;i<=n;i++) dist[i]=1000000; for(int i=0;i<n;i++) { if(dist[i]==1000000) continue; for(int j=i+1;j<=n;j++) { if(!cango[i][j]) continue; if(!checkgo(i,j,r)) dist[j]=min(dist[j],dist[i]+1); } if(dist[n]<=b) return true; } return false; } void solve_big() { bool res; for(int i=40;i>=0;i--) { res=testgo(i); if(res) { for(int j=0;j<n;j++) { for(int ii=j+1;ii<=n;ii++) { if(checkgo(j,ii,i)) cango[j][ii]=false; } } } else { tot|=(1ll<<i); } } } int main() { init(); if(a==1) { solve_big(); printf("%lld",tot); return 0; } ll ans[101][101]; for(int i=1;i<=n;i++) { ans[1][i]=qs[i]; } for(int i=2;i<=n;i++) { for(int j=i;j<=n;j++) { ans[i][j]=(1ll<<50); for(int ii=i-1;ii<j;ii++) { ans[i][j]=min(ans[i][j],ans[i-1][ii]|(qs[j]-qs[ii])); } } } ll fin_ans=(1ll<<50); for(int i=a;i<=b;i++) { fin_ans=min(fin_ans,ans[i][n]); } printf("%lld",fin_ans); return 0; }

Compilation message (stderr)

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