#include <bits/stdc++.h> #define IOSTREAM_BOOST true using namespace std; int n; int tab[500005]; int prefsum[500005]; set<pair<long long, int>> vals; long long valm = 0; int dp[500005]; int dpm = 0; int getDp(int x){ return (x >= 0 ? dp[x] : 0); } int main() { #if IOSTREAM_BOOST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cin >> n; for(int i = 0; i < n; i++) cin >> tab[i], prefsum[i + 1] = prefsum[i] + tab[i]; for(int i = 0; i < n; i++){ valm += tab[i]; pair<int, int> elem = {tab[i] - valm, getDp(i - 1) - dpm}; while(true){ auto ait = vals.lower_bound(elem); if(ait == vals.begin()) break; ait--; if(ait->second + dpm >= elem.second + dpm) vals.erase(ait); else break; } vals.insert(elem); auto it = vals.lower_bound({-valm, -1e9}); if(it != vals.end()) dp[i] = it->second + dpm; else dp[i] = 1e9; dpm++; } cout << (dp[n - 1] >= 1e9 ? -1 : dp[n - 1]) << "\n"; //for(int i = 0; i < n; i++) cout << dp[i] << " "; 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 | #include <bits/stdc++.h> #define IOSTREAM_BOOST true using namespace std; int n; int tab[500005]; int prefsum[500005]; set<pair<long long, int>> vals; long long valm = 0; int dp[500005]; int dpm = 0; int getDp(int x){ return (x >= 0 ? dp[x] : 0); } int main() { #if IOSTREAM_BOOST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cin >> n; for(int i = 0; i < n; i++) cin >> tab[i], prefsum[i + 1] = prefsum[i] + tab[i]; for(int i = 0; i < n; i++){ valm += tab[i]; pair<int, int> elem = {tab[i] - valm, getDp(i - 1) - dpm}; while(true){ auto ait = vals.lower_bound(elem); if(ait == vals.begin()) break; ait--; if(ait->second + dpm >= elem.second + dpm) vals.erase(ait); else break; } vals.insert(elem); auto it = vals.lower_bound({-valm, -1e9}); if(it != vals.end()) dp[i] = it->second + dpm; else dp[i] = 1e9; dpm++; } cout << (dp[n - 1] >= 1e9 ? -1 : dp[n - 1]) << "\n"; //for(int i = 0; i < n; i++) cout << dp[i] << " "; return 0; } |