Submission #76359

#TimeUsernameProblemLanguageResultExecution timeMemory
76359shoemakerjoBali Sculptures (APIO15_sculpture)C++14
100 / 100
170 ms1304 KiB
#include <bits/stdc++.h> using namespace std; #define maxn 2010 const int inf = 123456789; #define ll long long int N, A, B; ll nums[maxn]; ll pref = 0LL; bool dp[maxn][maxn]; //is it possible to end at some guy using exactly some other amount //use this dp table for N <= 100 //else we just want the minimum number int mym[maxn]; bool check(ll bit) { fill(mym, mym+maxn, inf); mym[0] = 0; for (int i = 1; i <= N; i++) { ll csum = 0; for (int j = i; j >= 1; j--) { csum += nums[j]; if ( (csum | pref) - pref >= bit) continue; mym[i] = min(mym[i], mym[j-1]+1); } } return mym[N] <= B; } void solve1() { for (int i = 50; i >= 0; i--) { ll cbit = 1LL << i; if (!check(cbit)) { pref += cbit; } } cout << pref << endl; } bool c2(ll bit) { for (int i = 0; i < 101; i++) { fill(dp[i], dp[i]+101, false); } dp[0][0] = true; for (int i = 1; i <= N; i++) { ll csum = 0LL; for (int j = i; j >= 1; j--) { csum += nums[j]; if ((csum | pref) - pref >= bit) continue; for (int k = 0; k <= N; k++) { dp[i][k] |= dp[j-1][k-1]; } } } for (int i = A; i <= B; i++) { if (dp[N][i]) return true; } return false; } void solve() { for (int i = 50; i >= 0; i--) { ll cbit = 1LL << i; if (!c2(cbit)) { pref += cbit; } } cout << pref << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> A >> B; for (int i = 1; i <= N; i++) { cin >> nums[i]; } // solve(); if (A == 1) solve1(); else solve(); }
#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...