Submission #185655

#TimeUsernameProblemLanguageResultExecution timeMemory
185655dndhkBali Sculptures (APIO15_sculpture)C++14
100 / 100
324 ms11128 KiB
#include <bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAX_N = 2000; const int INF = 10000000; int N, A, B; vector<ll> v; ll sum[MAX_N+1]; ll ans; ll Sum(ll x, ll y){ return sum[max(x, y)] - sum[min(x, y)-1]; } vector<int> gp[MAX_N+1]; bool chk1[MAX_N+1], chk2[MAX_N+1]; bool check(ll x){ for(int i=0; i<=N; i++){ while(!gp[i].empty()) gp[i].pop_back(); } for(int i=1; i<=N; i++){ for(int j=i; j<=N; j++){ if((Sum(i, j) | x) == x){ gp[i-1].pb(j); } } } for(int i=0; i<=N; i++) chk1[i] = chk2[i] = false; chk1[0] = true; for(int t=1; t<=B; t++){ for(int i=0; i<=N; i++){ if(chk1[i]){ for(int j : gp[i]){ chk2[j] = true; } } } for(int i=0; i<=N; i++){ chk1[i] = chk2[i]; chk2[i] = false; } if(t>=A && chk1[N]) return true; } return false; } void solve1(){ ans = (1LL<<40LL)-1; for(int k=39; k>=0; k--){ ll t = (1LL<<(ll)k); if(check(ans-t)){ ans-=t; } } } deque<int> dq; int dist[MAX_N+1]; bool check2(ll x){ for(int i=0; i<=N; i++){ while(!gp[i].empty()) gp[i].pop_back(); } for(int i=1; i<=N; i++){ for(int j=i; j<=N; j++){ if((Sum(i, j) | x) == x){ gp[i-1].pb(j); } } } for(int i=0; i<=N; i++) dist[i] = INF; dist[0] = 0; dq.pb(0); while(!dq.empty()){ int now = dq.front(); dq.pop_front(); for(int i : gp[now]){ if(dist[i]>dist[now]+1){ dist[i] = dist[now]+1; dq.pb(i); } } } return (dist[N]<=B); } void solve2(){ ans = (1LL<<45LL)-1; for(int k=44; k>=0; k--){ ll t = (1LL<<(ll)k); if(check2(ans-t)){ ans-=t; } } } int main(){ scanf("%d%d%d", &N, &A, &B); v.pb(0LL); for(int i=1 ;i<=N; i++){ ll x; scanf("%lld", &x); v.pb(x); sum[i]=sum[i-1]+v[i]; } if(A!=1) solve1(); else solve2(); cout<<ans; return 0; }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:106:7: 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:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x);
         ~~~~~^~~~~~~~~~~~
#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...