Submission #1059038

#TimeUsernameProblemLanguageResultExecution timeMemory
1059038sammyuriBali Sculptures (APIO15_sculpture)C++17
100 / 100
100 ms604 KiB
#include <bits/stdc++.h> using namespace std; /* suppose we are trying to satisfy prefix j let dp[i][0] be the minimum number of segments required to finish at i and dp[i][1] be the maximum we can do transitions in O(n^2) and check if dp[n][0] or dp[n][1] is good enough then we can build from the highest bit down overall: O(n^2 log y)? */ typedef long long ll; const ll LIMIT = (1ll << 61); const int MAXN = 2005; int n; int a, b; ll nums[MAXN]; ll dp[MAXN][2]; ll badmask; bool check() { for (int i = 0; i <= n; i ++) dp[i][0] = 1e9, dp[i][1] = -1; dp[0][0] = dp[0][1] = 0; for (int i = 0; i < n; i ++) { ll cursum = 0; for (int j = i + 1; j <= n; j ++) { cursum += nums[j]; // exceeded limit if (cursum >= LIMIT) break; if ((cursum & badmask) == 0) { dp[j][0] = min(dp[j][0], dp[i][0] + 1); dp[j][1] = max(dp[j][1], dp[i][1] + 1); } } } return (dp[n][0] <= b) && (dp[n][1] >= a); } int main() { cin >> n >> a >> b; for (int i = 1; i <= n; i ++) cin >> nums[i]; ll curbit = LIMIT / 2ll; badmask = 0; ll ans = 0; while (curbit) { badmask += curbit; if (!check()) { badmask -= curbit; ans += curbit; } curbit /= 2; } cout << ans << endl; }
#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...