#include<bits/stdc++.h> using namespace std; const long long INF = 1e18; int binSearch(vector<long long>& v, long long add){ int l = -1; int r = v.size() - 1; while(l < r){ int m = (l + 1 + r)/2; if(v[m] + add >= 0){ l = m; }else{ r = m-1; } } return l; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin>>n; vector<long long> city(n); for(int i = 0; i < n; i++){ cin>>city[i]; } vector<long long> dp; long long add = 0; dp.push_back(0); add += city[0]; for(int i = 1; i < n; i++){ int j = binSearch(dp, add); if(dp[dp.size() - 1] + add >= 0){ dp.push_back(-add); }else{ dp.push_back(-INF); } if(j >= 0){ dp[j+1] = -add; } add += city[i]; } int j = binSearch(dp, add); if(j == -1){ cout<<-1; }else{ int result = n - 1 - j; cout<<result; } 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 | #include<bits/stdc++.h> using namespace std; const long long INF = 1e18; int binSearch(vector<long long>& v, long long add){ int l = -1; int r = v.size() - 1; while(l < r){ int m = (l + 1 + r)/2; if(v[m] + add >= 0){ l = m; }else{ r = m-1; } } return l; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin>>n; vector<long long> city(n); for(int i = 0; i < n; i++){ cin>>city[i]; } vector<long long> dp; long long add = 0; dp.push_back(0); add += city[0]; for(int i = 1; i < n; i++){ int j = binSearch(dp, add); if(dp[dp.size() - 1] + add >= 0){ dp.push_back(-add); }else{ dp.push_back(-INF); } if(j >= 0){ dp[j+1] = -add; } add += city[i]; } int j = binSearch(dp, add); if(j == -1){ cout<<-1; }else{ int result = n - 1 - j; cout<<result; } return 0; } |