Submission #1127974

#TimeUsernameProblemLanguageResultExecution timeMemory
1127974heeheeheehaawBigger segments (IZhO19_segments)C++20
100 / 100
179 ms19864 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int v[500005]; pair<int, int> dp[500005]; signed main() { int n; cin>>n; cin>>v[1]; dp[1] = {v[1], 1}; priority_queue<pair<int, int>> pq; pq.push({-v[1] - v[1], 1}); int b = 0; for(int i = 2; i <= n; i++) { cin>>v[i]; v[i] += v[i - 1]; while(!pq.empty()) { pair<int, int> a = pq.top(); if(v[i] - v[a.second] < dp[a.second].first) break; pq.pop(); b = max(b, a.second); } dp[i] = {v[i] - v[b], dp[b].second + 1}; pq.push({-dp[i].first - v[i], i}); } cout<<dp[n].second<<'\n'; return 0; }
#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...