제출 #693083

#제출 시각아이디문제언어결과실행 시간메모리
693083taherBigger segments (IZhO19_segments)C++17
13 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; vector<array<long long, 2>> cur; int id = -1; void Insert(long long v, int j) { // keep the whole thing strictly increasing while (!cur.empty() && cur.back()[0] >= v) { cur.pop_back(); } cur.push_back({v, j}); return ; } int Query(int v) { while (id + 1 < (int) cur.size() && v >= cur[id + 1][0]) { ++id; } if (id >= 0) { return cur[id][1]; } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<long long> pref(a.begin(), a.end()); for (int i = 1; i < n; i++) { pref[i] += pref[i - 1]; } vector<array<long long, 2>> dp(n); dp[0] = {1, a[0]}; Insert(2LL * a[0], 0); for (int i = 1; i < n; i++) { dp[i] = dp[i - 1]; dp[i][1] += a[i]; int pos = Query(pref[i]); if (pos >= 0) { if (dp[i][0] < dp[pos][0] + 1) { dp[i][0] = dp[pos][0] + 1; dp[i][1] = pref[i] - pref[pos]; } else if (dp[i][0] == dp[pos][0] + 1) { dp[i][1] = min(dp[i][1], pref[i] - pref[pos]); } } Insert(dp[i][1] + pref[i], i); } cout << dp[n - 1][0] << '\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...