Submission #1192877

#TimeUsernameProblemLanguageResultExecution timeMemory
1192877lopkusBigger segments (IZhO19_segments)C++20
0 / 100
32 ms78664 KiB
#include <bits/stdc++.h> #define int64_t int const int N = 5e6 + 15; std::pair<int, int> t[N]; std::vector<int> ll(N), rr(N); std::pair<int, int> neutral = {-1, -1}; const int64_t MAXN = 1e15; struct implicit { int idxx = 1; implicit() { for (int i = 0; i < N; i++) { t[i] = neutral; } } void update(int node, int tl, int tr, int index, std::pair<int, int> value) { if (tl == tr) { t[node] = value; return; } int tm = (tl + tr) / 2; if (index <= tm) { if (!ll[node]) ll[node] = ++idxx; update(ll[node], tl, tm, index, value); } else { if (!rr[node]) rr[node] = ++idxx; update(rr[node], tm + 1, tr, index, value); } t[node] = std::max((ll[node] ? t[ll[node]] : neutral), (rr[node] ? t[rr[node]] : neutral)); } std::pair<int, int> query(int node, int tl, int tr, int l, int r) { if (l > tr || r < tl) return neutral; if (l <= tl && tr <= r) return t[node]; int tm = (tl + tr) / 2; std::pair<int, int> ans = neutral; ans = std::max(ans, query(ll[node], tl, tm, l, r)); ans = std::max(ans, query(rr[node], tm + 1, tr, l, r)); return ans; } } seg; void solve() { int n; std::cin >> n; std::vector<int64_t> a(n + 1); for(int i = 1; i <= n; i++) { std::cin >> a[i]; } std::vector<int64_t> pref(n + 1); for(int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + a[i]; } std::vector<std::pair<int,int>> dp(n + 1, {- 1, - 1}); dp[0] = {0, 0}; for(int i = 1; i <= n; i++) { for(int j = i - 1; j >= 0; j--) { if(pref[i] >= pref[j] + dp[j].second) { dp[i] = std::max(dp[i], {dp[j].first + 1, dp[j].second}); } } if(dp[i].first == - 1) { dp[i].first = dp[i - 1].first; dp[i].second = dp[i - 1].second + a[i]; } else { dp[i].second = pref[i] - dp[i].second; } } std::cout << dp[n].first; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t = 1; //std::cin >> t; while (t--) { solve(); } return 0; }

Compilation message (stderr)

segments.cpp:12:22: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   12 | const int64_t MAXN = 1e15;
      |                      ^~~~
#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...