Submission #517304

#TimeUsernameProblemLanguageResultExecution timeMemory
517304CodeTiger927Bali Sculptures (APIO15_sculpture)C++17
100 / 100
219 ms4348 KiB
using namespace std; #include <iostream> #include <cstring> #define MAXN 2005 int N,A,B; long long a[MAXN],pref[MAXN],dp2[MAXN]; bool dp[MAXN][MAXN]; void solve() { long long pre = 0; for(int i = 60;i >= 0;--i) { long long r = pre + (1ll << i) - 1; // cout << pre << " " << l << " " << r << endl; memset(dp,0,sizeof(dp)); dp[0][0] = true; for(int j = 1;j <= N;++j) { for(int k = 1;k <= N;++k) { for(int t = 0;t < j;++t) { if(dp[t][k - 1] && ((pref[j] - pref[t]) | r) == r) { dp[j][k] = true; break; } } } } bool uwu = false; for(int j = A;j <= B;++j) { uwu |= dp[N][j]; } if(!uwu) { pre |= (1ll << i); } } cout << pre << endl; } void solve2() { long long pre = 0; for(int i = 60;i >= 0;--i) { long long r = pre + (1ll << i) - 1; // cout << pre << " " << l << " " << r << endl; dp2[0] = 0; for(int j = 1;j <= N;++j) { dp2[j] = N + 1; for(int k = 0;k < j;++k) { if(((pref[j] - pref[k]) | r) == r) { dp2[j] = min(dp2[j],dp2[k] + 1); } } } if(dp2[N] > B) { pre |= (1ll << i); } } cout << pre << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> A >> B; for(int i = 0;i < N;++i) { cin >> a[i]; pref[i + 1] = a[i] + pref[i]; } if(N <= 100) { solve(); }else{ solve2(); } return 0; }
#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...