제출 #861003

#제출 시각아이디문제언어결과실행 시간메모리
861003AlfraganusBigger segments (IZhO19_segments)C++14
13 / 100
1 ms600 KiB
#include <bits/stdc++.h> using namespace std; #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) 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); int x = 0; for(int i = 0; i < n; i ++){ int l = x, 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; if(dp[i + 1] > dp[i]) x = l; sum[i + 1] = pre[i + 1] - pre[l]; } cout << dp[n]; } signed main() { 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...