Submission #1198450

#TimeUsernameProblemLanguageResultExecution timeMemory
1198450aykhnBigger segments (IZhO19_segments)C++20
100 / 100
64 ms27796 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define inf 0x3F3F3F3F3F3F3F3F const int MXN = 5e5 + 5; const int mod = 1e9 + 7; array<int, 2> dp[MXN]; void _() { int n; cin >> n; int a[n + 1], p[n + 1]; for (int i = 1; i <= n; i++) cin >> a[i]; p[0] = 0; for (int i = 1; i <= n; i++) p[i] = (i ? p[i - 1] : 0) + a[i]; auto sum = [&](int l, int r) { if (l > r) return 0LL; return p[r] - (l ? p[l - 1] : 0LL); }; dp[0] = {0, 0}; priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq; pq.push({0, 0}); array<int, 2> cur = {0, 0}; for (int i = 1; i <= n; i++) { while (!pq.empty() && pq.top()[0] <= p[i]) { int j = pq.top()[1]; pq.pop(); if (dp[j][0] + 1 < cur[0]) continue; if (dp[j][0] + 1 > cur[0]) cur = {dp[j][0] + 1, -p[j]}; else if (-p[j] <= cur[1]) cur[1] = -p[j]; } dp[i] = {cur[0], cur[1] + p[i]}; pq.push({dp[i][1] + p[i], i}); } cout << dp[n][0] << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) _(); }
#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...