Submission #861664

#TimeUsernameProblemLanguageResultExecution timeMemory
861664AndreiBOTOBali Sculptures (APIO15_sculpture)C++14
100 / 100
66 ms2796 KiB
#include <bits/stdc++.h> #pragma optimize GCC ("Ofast") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") ///#include <tryhardmode> ///#include <GODMODE::ON> using namespace std; #define int long long const int NMAX=2e3+5; const int MASK=50; bool dp1[NMAX][NMAX]; int dp2[NMAX]; int v[NMAX]; int n,a,b; bool valid_dp1(long long mask,int bit) { int i,j,k; long long s=0; for(i=1;i<=n;i++) for(j=0;j<=b;j++) dp1[i][j]=false; dp1[0][0]=true; for(i=0;i<n;i++) { for(j=0;j<=b;j++) { s=0; for(k=i+1;k<=n;k++) { s+=v[k]; if((((mask>>bit) & (s>>bit))^ (s>>bit))==0) dp1[k][j+1]|=dp1[i][j]; } } } for(i=a;i<=b;i++) if(dp1[n][i]==true) return true; return false; } long long get_ans1() { long long mask=0; int i; for(i=49;i>=0;i--) { if(valid_dp1(mask,i)==false) mask=mask^(1LL<<i); } return mask; } void solve1() { cout<<get_ans1(); } bool valid_dp2(long long mask,int bit) { int i,j,k; long long s=0; for(i=1;i<=n;i++) dp2[i]=b+1; dp2[0]=0; for(i=0;i<n;i++) { s=0; for(k=i+1;k<=n;k++) { s+=v[k]; if((((mask>>bit) & (s>>bit))^ (s>>bit))==0) dp2[k]=min(dp2[k],dp2[i]+1); } } if(dp2[n]<=b) return true; return false; } long long get_ans2() { long long mask=0; int i; for(i=49;i>=0;i--) { if(valid_dp2(mask,i)==false) mask=mask^(1LL<<i); } return mask; } void solve2() { cout<<get_ans2(); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>a>>b; for(int i=1;i<=n;i++) cin>>v[i]; if(a!=1) solve1(); else solve2(); return 0; }

Compilation message (stderr)

sculpture.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
    3 | #pragma optimize GCC ("Ofast")
      | 
sculpture.cpp: In function 'bool valid_dp2(long long int, long long int)':
sculpture.cpp:69:11: warning: unused variable 'j' [-Wunused-variable]
   69 |     int i,j,k;
      |           ^
#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...