Submission #1066147

#TimeUsernameProblemLanguageResultExecution timeMemory
1066147aufanBigger segments (IZhO19_segments)C++17
100 / 100
61 ms20932 KiB
#include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; vector<int> p(n + 1); for (int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i]; vector<int> dp(n + 1), lst(n + 2); for (int i = 1; i <= n; i++) { lst[i] = max(lst[i], lst[i - 1]); dp[i] = dp[lst[i]] + 1; int j = lower_bound(p.begin(), p.end(), 2 * p[i] - p[lst[i]]) - p.begin(); lst[j] = i; } cout << dp[n] << '\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...