제출 #1107914

#제출 시각아이디문제언어결과실행 시간메모리
1107914alex_2008Bigger segments (IZhO19_segments)C++14
100 / 100
200 ms36476 KiB
#include <bits/stdc++.h> #define ff first #define ss second typedef long long ll; using namespace std; const int N = 5e5 + 10; const ll INF = 2e18 + 10; ll pref[N]; pair <ll, ll> dp[N]; ll dpp[N]; ll tree[4 * N]; int n; void upd(int v, int tl, int tr, int pos, ll val) { if (tl == tr) { tree[v] = val; return; } int tm = (tl + tr) / 2; if (pos <= tm) upd(2 * v, tl, tm, pos, val); else upd(2 * v + 1, tm + 1, tr, pos, val); tree[v] = min(tree[2 * v], tree[2 * v + 1]); } int get(ll p) { int v = 1, tl = 1, tr = n + 1; while (tl != tr) { int tm = (tl + tr) / 2; if (tree[2 * v + 1] <= p) { v = 2 * v + 1; tl = tm + 1; } else { v = 2 * v; tr = tm; } } return tl; } int main() { cin >> n; for (int i = 1; i <= 4 * n + 4; i++) { tree[i] = INF; } for (int i = 1; i <= n; i++) { cin >> pref[i]; pref[i] += pref[i - 1]; } dp[0] = { 0, 0 }; dpp[0] = 0; upd(1, 1, n + 1, 0 + 1, dpp[0]); for (int i = 1; i <= n; i++) { int ind = get(pref[i]) - 1; dp[i] = { dp[ind].first + 1, pref[i] - pref[ind] }; dpp[i] = dp[i].ss + pref[i]; upd(1, 1, n + 1, i + 1, dpp[i]); } cout << dp[n].ff << "\n"; }
#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...