제출 #678132

#제출 시각아이디문제언어결과실행 시간메모리
678132AlcabelBigger segments (IZhO19_segments)C++17
13 / 100
1 ms212 KiB
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; vector<int> a(n); vector<long long> pref(n + 1); for (int i = 0; i < n; ++i) { cin >> a[i]; pref[i + 1] = pref[i] + a[i]; } vector<pair<int, long long>> f(n + 1); f[0] = {0, 0}; for (int i = 1; i <= n; ++i) { int l = 0, r = i; while (r - l > 1) { int m = l + (r - l) / 2; if (f[m].second <= pref[i] - pref[m]) { l = m; } else { r = m; } } f[i] = {f[l].first + 1, pref[i] - pref[l]}; } cout << f[n].first << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T = 1; // cin >> T; while (T--) { solve(); } 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...