Submission #332414

#TimeUsernameProblemLanguageResultExecution timeMemory
332414keko37Bigger segments (IZhO19_segments)C++14
100 / 100
108 ms24824 KiB
#include<bits/stdc++.h> using namespace std; typedef long long llint; typedef pair <int, int> pi; const int MAXN = 500005; int n; llint a[MAXN], sum[MAXN], best[MAXN], sol[MAXN], mx[MAXN]; int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum[i] = a[i] + sum[i - 1]; } for (int i = 1; i <= n; i++) { mx[i] = max(mx[i], mx[i - 1]); sol[i] = 1 + sol[mx[i]]; best[i] = sum[i] - sum[mx[i]]; int ind = lower_bound(sum, sum + n + 1, best[i] + sum[i]) - sum; mx[ind] = max(mx[ind], (llint) i); } cout << sol[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...