#include <bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX=5e5+5; const int inf=1e18+9; int a[MAX]; int pref[MAX]; int dp[MAX]; int sum(int l,int r){ return pref[r]-pref[l-1]; } set<pii>pom; // suma, wartosc dp int query(int x){ if (pom.empty())return -inf; auto it=*pom.begin(); if (it.st>x)return -inf; //cout<<"HIHI\n"; auto iter=*(--pom.upper_bound(mp(x,inf))); return iter.nd+1; } void update(int num,int cost){ if (pom.empty()){pom.insert(mp(num,cost));return;} // wywalamy z gory while (true){ if (pom.empty())break; if (pom.upper_bound(mp(num-1,inf))==pom.end())break; auto it=*pom.upper_bound(mp(num-1,inf)); if (it.nd<=cost)pom.erase(it); else break; } if (pom.empty()){pom.insert(mp(num,cost));return;} auto iter=*pom.begin(); if (num<iter.st){pom.insert(mp(num,cost));return;} auto it=*(--pom.lower_bound(mp(num,inf))); if (it.nd<cost) pom.insert(mp(num,cost)); } int32_t main(){ BOOST; int n; cin>>n; for (int i=1;i<=n;i++)cin>>a[i],pref[i]=pref[i-1]+a[i]; for (int i=1;i<=n;i++){ dp[i]=-inf; dp[i]=max(dp[i],query(pref[i])); if (pref[i]>=0)dp[i]=max(dp[i],0LL); if (dp[i]>=0){ update(pref[i],dp[i]); } /* cout<<"ZAWARTOSC "<<i<<"\n"; for (auto it:pom)cout<<"TERAZ "<<it.st<<" "<<it.nd<<"\n"; cout<<"SHIT "<<i<<" "<<dp[i]<<"\n"; */ } /* for (int i=1;i<=n;i++){ cout<<"TERAZ "<<i<<" "<<dp[i]<<"\n"; } */ if (dp[n]<0)cout<<"-1"; else cout<<n-dp[n]-1; 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 | #include <bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX=5e5+5; const int inf=1e18+9; int a[MAX]; int pref[MAX]; int dp[MAX]; int sum(int l,int r){ return pref[r]-pref[l-1]; } set<pii>pom; // suma, wartosc dp int query(int x){ if (pom.empty())return -inf; auto it=*pom.begin(); if (it.st>x)return -inf; //cout<<"HIHI\n"; auto iter=*(--pom.upper_bound(mp(x,inf))); return iter.nd+1; } void update(int num,int cost){ if (pom.empty()){pom.insert(mp(num,cost));return;} // wywalamy z gory while (true){ if (pom.empty())break; if (pom.upper_bound(mp(num-1,inf))==pom.end())break; auto it=*pom.upper_bound(mp(num-1,inf)); if (it.nd<=cost)pom.erase(it); else break; } if (pom.empty()){pom.insert(mp(num,cost));return;} auto iter=*pom.begin(); if (num<iter.st){pom.insert(mp(num,cost));return;} auto it=*(--pom.lower_bound(mp(num,inf))); if (it.nd<cost) pom.insert(mp(num,cost)); } int32_t main(){ BOOST; int n; cin>>n; for (int i=1;i<=n;i++)cin>>a[i],pref[i]=pref[i-1]+a[i]; for (int i=1;i<=n;i++){ dp[i]=-inf; dp[i]=max(dp[i],query(pref[i])); if (pref[i]>=0)dp[i]=max(dp[i],0LL); if (dp[i]>=0){ update(pref[i],dp[i]); } /* cout<<"ZAWARTOSC "<<i<<"\n"; for (auto it:pom)cout<<"TERAZ "<<it.st<<" "<<it.nd<<"\n"; cout<<"SHIT "<<i<<" "<<dp[i]<<"\n"; */ } /* for (int i=1;i<=n;i++){ cout<<"TERAZ "<<i<<" "<<dp[i]<<"\n"; } */ if (dp[n]<0)cout<<"-1"; else cout<<n-dp[n]-1; return 0; } |