#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5+10; const long long INF=(1ll<<60); int n; long long a[MAXN], s, pr[MAXN], dp[MAXN]; pair <long long, int> p[MAXN]; long long d[8*MAXN+10], rr; void akt(int u, long long v) { u+=rr-1; while(u) { d[u]=min(d[u], v); u>>=1; } } long long zap(int u, int v) { u+=rr-1; v+=rr-1; long long ans=INF; while(u<v) { if(u&1) { ans=min(ans, d[u]); u>>=1; ++u; } else { u>>=1; } if(v&1) { v>>=1; } else { ans=min(ans, d[v]); v>>=1; --v; } } if(u==v) { ans=min(ans, d[u]); } return ans; } int main() { scanf("%d", &n); rr=1; while(rr<n+10) { rr<<=1; } for(int i=1; i<2*rr; ++i) { d[i]=INF; } for(int i=1; i<=n; ++i) { scanf("%lld", &a[i]); s+=a[i]; } if(s<0) { printf("-1\n"); return 0; } for(int i=1; i<=n; ++i) { pr[i]=pr[i-1]+a[i]; } for(int i=0; i<=n; ++i) { p[i]={pr[i], i}; } sort(p, p+n+1); long long pre=p[0].first, licz=1; for(int i=0; i<=n; ++i) { if(p[i].first!=pre) { ++licz; } pr[p[i].second]=licz; pre=p[i].first; } akt(pr[0], 0); dp[0]=0; for(int i=1; i<=n; ++i) { dp[i]=zap(1, pr[i])-1+i; akt(pr[i], dp[i]-i); } printf("%lld\n", dp[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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | #include <bits/stdc++.h> using namespace std; const int MAXN = 5e5+10; const long long INF=(1ll<<60); int n; long long a[MAXN], s, pr[MAXN], dp[MAXN]; pair <long long, int> p[MAXN]; long long d[8*MAXN+10], rr; void akt(int u, long long v) { u+=rr-1; while(u) { d[u]=min(d[u], v); u>>=1; } } long long zap(int u, int v) { u+=rr-1; v+=rr-1; long long ans=INF; while(u<v) { if(u&1) { ans=min(ans, d[u]); u>>=1; ++u; } else { u>>=1; } if(v&1) { v>>=1; } else { ans=min(ans, d[v]); v>>=1; --v; } } if(u==v) { ans=min(ans, d[u]); } return ans; } int main() { scanf("%d", &n); rr=1; while(rr<n+10) { rr<<=1; } for(int i=1; i<2*rr; ++i) { d[i]=INF; } for(int i=1; i<=n; ++i) { scanf("%lld", &a[i]); s+=a[i]; } if(s<0) { printf("-1\n"); return 0; } for(int i=1; i<=n; ++i) { pr[i]=pr[i-1]+a[i]; } for(int i=0; i<=n; ++i) { p[i]={pr[i], i}; } sort(p, p+n+1); long long pre=p[0].first, licz=1; for(int i=0; i<=n; ++i) { if(p[i].first!=pre) { ++licz; } pr[p[i].second]=licz; pre=p[i].first; } akt(pr[0], 0); dp[0]=0; for(int i=1; i<=n; ++i) { dp[i]=zap(1, pr[i])-1+i; akt(pr[i], dp[i]-i); } printf("%lld\n", dp[n]); return 0; } |