Submission #1204981

#TimeUsernameProblemLanguageResultExecution timeMemory
1204981ofozBigger segments (IZhO19_segments)C++17
37 / 100
1592 ms3400 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define vi vector<int> vector<int> a; vector<int> prfx; vector< vector<int> > memo; set<pi> prv; int mx = 0; /* sum(j+1, i) >= a_j sum(j+1, i) - a_j >= 0 sum(j+1, i) - a_j - sum(0, i) >= -sum(0, i) -sum(0, j) - a_j >= -sum(0, i) sum(0, j) + a_j <= sum(0, i) */ int getPrfx(int l, int r) { int left = (l == 0) ? 0 : prfx[l - 1]; int right = prfx[r]; return right - left; } bool compare(pi a, pi b) { if (a.first > b.first) return true; if (a.first < b.first) return false; if (a.second < b.second) return true; return false; } signed main() { int n; cin >> n; a.resize(n); for (int i = 0; i < n; ++i) cin >> a[i]; prfx.resize(n); prfx[0] = a[0]; for (int i = 1; i < n; ++i) { prfx[i] = prfx[i - 1] + a[i]; } vector<pi> dp(n+1, {-INT32_MAX, INT32_MAX}); dp[0] = {1, 0}; for (int i = 0; i < n; i++) { int x = a[i]; pi res = dp[i]; res.second += x; for (int j = 0; j < i; j++) { pi c = dp[j+1]; //cerr << j+1 << ' ' << i << ' ' << getPrfx(j, i-1) << endl; int s = getPrfx(j+1, i); if (s < c.second) continue; c.second = s; c.first++; if (compare(c, res)) res = c; } dp[i+1] = res; } cout << dp[n].first; }
#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...