#include<bits/stdc++.h> typedef long long ll; typedef std::pair<ll, ll> pll; typedef std::pair<int, int> pii; #define all(x) (x).begin(),(x).end() #define debug std::cout<<"ok"<<std::endl const ll INF=1e9; int solve (const std::vector<int> &V, int i) { std::vector<pll> K1(1, {0,0}), K2(1, {0,0}); for (int k=i-1; k>=0; k--) K1.push_back({K1.back().first+V[k], K1.back().second+1}); for (int k=i+1; k<V.size(); k++) K2.push_back({K2.back().first+V[k], K2.back().second+1}); std::sort(all(K1)); std::sort(all(K2)); ll W=INF; std::vector<int> TEMP; for (auto a:K1) { auto t=std::lower_bound(all(K2), pll{-V[i]-a.first,ll(0)}); if (t==K2.end()) continue; int it=t-K2.begin(); ll min=K2[it].second; for (int k=it; k<K2.size(); k++) if (K2[k].second<min) { min=K2[k].second; it=k; } TEMP.clear(); int y=-1; ll J=0; for (int k=0; k<i-a.second; k++) { J+=V[k]; TEMP.push_back(V[k]); if (y<0 && V[k]<0) y=TEMP.size()-1; } TEMP.push_back(a.first+V[i]+K2[it].first); for (int k=i+K2[it].second+1; k<V.size(); k++) { J+=V[k]; TEMP.push_back(V[k]); if (y<0 && V[k]<0) y=TEMP.size()-1; } if (y<0) { W=std::min(a.second+K2[it].second, W); continue; } else W=std::min(W, solve(TEMP, y)+a.second+K2[it].second); } return W; } main () { int n; std::cin>>n; std::vector<int> V(n); int r=-1; ll W=0; for (int i=0; i<n; i++) { std::cin>>V[i]; W+=V[i]; if (r<0 && V[i]<0) r=i; } if (W<0) std::cout<<-1<<std::endl; else if (r<0) std::cout<<0<<std::endl; else { std::cout<<solve(V, r)<<std::endl; } }
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 | #include<bits/stdc++.h> typedef long long ll; typedef std::pair<ll, ll> pll; typedef std::pair<int, int> pii; #define all(x) (x).begin(),(x).end() #define debug std::cout<<"ok"<<std::endl const ll INF=1e9; int solve (const std::vector<int> &V, int i) { std::vector<pll> K1(1, {0,0}), K2(1, {0,0}); for (int k=i-1; k>=0; k--) K1.push_back({K1.back().first+V[k], K1.back().second+1}); for (int k=i+1; k<V.size(); k++) K2.push_back({K2.back().first+V[k], K2.back().second+1}); std::sort(all(K1)); std::sort(all(K2)); ll W=INF; std::vector<int> TEMP; for (auto a:K1) { auto t=std::lower_bound(all(K2), pll{-V[i]-a.first,ll(0)}); if (t==K2.end()) continue; int it=t-K2.begin(); ll min=K2[it].second; for (int k=it; k<K2.size(); k++) if (K2[k].second<min) { min=K2[k].second; it=k; } TEMP.clear(); int y=-1; ll J=0; for (int k=0; k<i-a.second; k++) { J+=V[k]; TEMP.push_back(V[k]); if (y<0 && V[k]<0) y=TEMP.size()-1; } TEMP.push_back(a.first+V[i]+K2[it].first); for (int k=i+K2[it].second+1; k<V.size(); k++) { J+=V[k]; TEMP.push_back(V[k]); if (y<0 && V[k]<0) y=TEMP.size()-1; } if (y<0) { W=std::min(a.second+K2[it].second, W); continue; } else W=std::min(W, solve(TEMP, y)+a.second+K2[it].second); } return W; } main () { int n; std::cin>>n; std::vector<int> V(n); int r=-1; ll W=0; for (int i=0; i<n; i++) { std::cin>>V[i]; W+=V[i]; if (r<0 && V[i]<0) r=i; } if (W<0) std::cout<<-1<<std::endl; else if (r<0) std::cout<<0<<std::endl; else { std::cout<<solve(V, r)<<std::endl; } } |