Submission #1204988

#TimeUsernameProblemLanguageResultExecution timeMemory
1204988ofozBigger segments (IZhO19_segments)C++17
13 / 100
2 ms328 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; /* 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) 2 + 2 <= 5 4 <= 5 */ 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; } pi findIndex(int i, vi& a, vector<pi>& dp, set<pi> prv) { int s1 = getPrfx(0, i); auto it = prv.upper_bound({s1, INT64_MAX}); if (prv.empty() || it == prv.begin()) { return {INT32_MIN, -1}; } int j = (--it)->second; int s2 = getPrfx(j+1, i); pi c = {dp[j+1].first+1, s2}; return c; } 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, {-INT64_MAX, INT64_MAX}); dp[0] = {1, 0}; int mx = 1; set<pi> prv; set<pi> prv2; for (int i = 0; i < n; i++) { int x = a[i]; pi res = dp[i]; res.second += x; pi c1 = findIndex(i, a, dp, prv); pi c2 = findIndex(i, a, dp, prv2); if (compare(c1, res)) res = c1; if (compare(c2, res)) res = c2; dp[i+1] = res; if (res.first > mx) { mx = res.first; prv2 = prv; prv.clear(); } int s1 = getPrfx(0, i); prv.insert({s1 + res.second, i}); /* 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; } */ } 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...