#include <bits/stdc++.h> using namespace std; typedef long long int LL; const int MAXN = 500005; const LL INF = 10000000000000000LL; int n; LL A[MAXN], pref_sum[MAXN]; LL dp[MAXN]; map<LL,LL> M; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> A[i]; pref_sum[i] = pref_sum[i-1] + A[i]; } dp[0] = 0; for (int i = 1; i <= n; i++) dp[i] = INF; M[INF] = -INF; M[0] = 0; for (int i = 1; i <= n; i++) { if (A[i] >= 0) dp[i] = min(dp[i], dp[i-1]); if (pref_sum[i] >= 0) { map<LL,LL>::iterator bit = M.upper_bound(pref_sum[i]); bit--; dp[i] = min(dp[i], i + bit->second - 1); LL i_contrib = dp[i] - i; while (true) { map<LL,LL>::iterator rit = M.lower_bound(pref_sum[i]); if (rit->second >= i_contrib) M.erase(rit); else break; } M[pref_sum[i]] = i_contrib; } } if (dp[n] >= INF) { cout << "-1\n"; return 0; } cout << dp[n] << "\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <bits/stdc++.h> using namespace std; typedef long long int LL; const int MAXN = 500005; const LL INF = 10000000000000000LL; int n; LL A[MAXN], pref_sum[MAXN]; LL dp[MAXN]; map<LL,LL> M; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> A[i]; pref_sum[i] = pref_sum[i-1] + A[i]; } dp[0] = 0; for (int i = 1; i <= n; i++) dp[i] = INF; M[INF] = -INF; M[0] = 0; for (int i = 1; i <= n; i++) { if (A[i] >= 0) dp[i] = min(dp[i], dp[i-1]); if (pref_sum[i] >= 0) { map<LL,LL>::iterator bit = M.upper_bound(pref_sum[i]); bit--; dp[i] = min(dp[i], i + bit->second - 1); LL i_contrib = dp[i] - i; while (true) { map<LL,LL>::iterator rit = M.lower_bound(pref_sum[i]); if (rit->second >= i_contrib) M.erase(rit); else break; } M[pref_sum[i]] = i_contrib; } } if (dp[n] >= INF) { cout << "-1\n"; return 0; } cout << dp[n] << "\n"; return 0; } |