#include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long int> energy(n+1); for(int i = 1; i <= n; i++) { cin >> energy[i]; } vector<long long int> prefixSum(n+1); for(int i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i-1] + energy[i]; } vector<long long int> dp(n+1, LONG_LONG_MAX); map<long long int, long long int> M; dp[0] = 0; M[0] = -1; for(int i = 1; i <= n; i++) { long long int key = prefixSum[i-1]; long long int val = dp[i-1] - i; if(dp[i-1] < LONG_LONG_MAX) { auto it = M.lower_bound(key); while(it != M.end()) { if(it->second > val) { it = M.erase(it); } else { break; } } M[key] = val; } auto ub = M.upper_bound(prefixSum[i]); if(ub != M.begin()) { ub--; if(prefixSum[i] - ub->first >= 0) { dp[i] = ub->second + i; } } } dp[n] <= n + 2? cout << dp[n] << endl : cout << -1 << 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 | #include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long int> energy(n+1); for(int i = 1; i <= n; i++) { cin >> energy[i]; } vector<long long int> prefixSum(n+1); for(int i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i-1] + energy[i]; } vector<long long int> dp(n+1, LONG_LONG_MAX); map<long long int, long long int> M; dp[0] = 0; M[0] = -1; for(int i = 1; i <= n; i++) { long long int key = prefixSum[i-1]; long long int val = dp[i-1] - i; if(dp[i-1] < LONG_LONG_MAX) { auto it = M.lower_bound(key); while(it != M.end()) { if(it->second > val) { it = M.erase(it); } else { break; } } M[key] = val; } auto ub = M.upper_bound(prefixSum[i]); if(ub != M.begin()) { ub--; if(prefixSum[i] - ub->first >= 0) { dp[i] = ub->second + i; } } } dp[n] <= n + 2? cout << dp[n] << endl : cout << -1 << endl; } |