Submission #860491

#TimeUsernameProblemLanguageResultExecution timeMemory
860491AlfraganusBigger segments (IZhO19_segments)C++14
13 / 100
1 ms436 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define fs first #define ss second #define str string #define all(a) a.begin(), a.end() #define print(a) \ for (auto x : a) \ cout << x << ' '; \ cout << endl; #define each(x, a) for (auto x : a) struct node { int s, l, r; }; void solve() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i ++) cin >> a[i]; vector<int> pre(n + 1); for(int i = 0; i < n; i ++) pre[i + 1] = pre[i] + a[i]; vector<int> dp(n + 1), sum(n + 1); for(int i = 0; i < n; i ++){ int l = 0, r = i; while(l < r){ int m = (l + r + 1) >> 1; if(pre[i + 1] - pre[m] >= sum[m]) l = m; else r = m - 1; } dp[i + 1] = dp[l] + 1; sum[i + 1] = pre[i + 1] - pre[l]; } cout << dp[n]; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) { solve(); cout << endl; } }
#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...