Submission #33731

#TimeUsernameProblemLanguageResultExecution timeMemory
33731sinhrivBali Sculptures (APIO15_sculpture)C++14
100 / 100
93 ms10120 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2030; int n, a, b; int f[N]; int arr[N]; long long sum[N]; void small(){ long long ans = sum[n]; for(int mask = 0; mask < (1 << (n - 1)); ++mask){ int cnt = __builtin_popcount(mask) + 1; if(cnt < a || cnt > b) continue; long long curr = 0, now = 0; for(int i = 1; i <= n; ++i){ curr += arr[i]; if(mask & (1 << (i - 1))){ now |= curr; curr = 0; } } now |= curr; ans = min(ans, now); } cout << ans; } void Medium(){ for(int value = 0; value < (1 << 11); ++value){ memset(f, 60, sizeof f); f[0] = 0; for(int i = 1; i <= n; ++i){ for(int j = i - 1; j >= 0; --j){ if((value | (sum[i] - sum[j])) == value){ f[i] = min(f[i], f[j] + 1); } } } if(f[n] <= b){ cout << value; return; } } } bool g[N][N]; bool now[N][N]; void Big(){ memset(g, true, sizeof g); long long ans = 0; for(int bit = 40; bit >= 0; --bit){ memset(now, false, sizeof now); now[0][0] = true; for(int i = 1; i <= n; ++i){ for(int j = 1; j <= i; ++j){ if(g[i][j] == false) continue; for(int k = i - 1; k >= j - 1; --k){ long long tot = sum[i] - sum[k]; tot = ((ans | tot) ^ ans); tot = (tot >= (1LL << bit)); if(now[k][j - 1] == true && tot == 0){ now[i][j] = true; break; } } } } bool fine = false; for(int x = a; x <= b; ++x){ if(now[n][x]){ fine = true; break; } } if(!fine){ ans += (1LL << bit); } else{ for(int i = 0; i <= n; ++i){ for(int j = 0; j <= n; ++j){ g[i][j] = now[i][j]; } } } } cout << ans << endl; } int p[N]; int q[N]; int sz = 0; int lst[N]; void Biggest(){ long long ans = 0; for(int bit = 41; bit >= 0; --bit){ memset(p, 60, sizeof p); p[0] = 0; sz = 0; lst[++sz] = 0; for(int i = 1; i <= n; ++i){ if(q[i] > b) continue; for(int it = 1; it <= sz; ++it){ int j = lst[it]; long long tot = sum[i] - sum[j]; tot = (ans | tot) ^ ans; tot = (tot < (1LL << bit)); if(tot){ p[i] = min(p[i], p[j] + 1); } } if(p[i] <= b) lst[++sz] = i; } if(p[n] <= b){ for(int i = 1; i <= n; ++i){ q[i] = p[i]; } } else{ ans += (1LL << bit); } } cout << ans << endl; } int main(){ if(fopen("1.inp", "r")){ freopen("1.inp", "r", stdin); } cin >> n >> a >> b; for(int i = 1; i <= n; ++i){ cin >> arr[i]; sum[i] = arr[i] + sum[i - 1]; } if(n <= 20) small(); else{ if(sum[n] <= 2000 && n <= 100) Medium(); else if(n <= 100) Big(); else{ Biggest(); } } return 0; }

Compilation message (stderr)

sculpture.cpp: In function 'int main()':
sculpture.cpp:159:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
#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...