#include <iostream> #include <vector> using namespace std; const int N = 1 << 19; int n; long long A[N]; vector<int> B; long long Pref[N]; int Prev[N]; int Dp[N]; void init() { cin >> n; bool negative = 0; B.push_back(0); for (int i=1; i<=n; i++) { cin >> A[i]; Pref[i] = Pref[i-1] + A[i]; if (A[i] != 0) { B.push_back(i); } if (A[i] < 0) { negative = 1; } if (negative == 1) { Dp[i] = N; } if (A[i-1] != 0) { Prev[i] = i - 1; } else { Prev[i] = Prev[i-1]; } } } void solve() { int last = -1; for (int i=1; i<B.size(); i++) { if (A[B[i]] < 0) { for (int j=1; j<i; j++) { if (Pref[B[i]] - Pref[B[j]-1] >= 0) { Dp[B[i]] = min(Dp[B[i]], B[i] - B[j] + Dp[Prev[B[j]]]); } } last = i; } if (A[B[i]] > 0 && Dp[B[i]] > 0) { for (int j=1; j<=last; j++) { if (Pref[B[i]] - Pref[B[j]-1] >= 0) { Dp[B[i]] = min(min(Dp[B[i]], Dp[B[i-1]]), B[i] - B[j] + Dp[Prev[B[j]]]); } } } } /* for (int i=0; i<B.size(); i++) { cout << Dp[B[i]] << ' '; } cout << '\n'; */ int mini = N; for (int i=B.size()-1; i>=0; i--) { mini = min(mini, Dp[B[i]]); if (A[B[i]] < 0) { break; } } if (Pref[n] < 0) { cout << "-1\n"; } else { cout << mini << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(); solve(); 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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | #include <iostream> #include <vector> using namespace std; const int N = 1 << 19; int n; long long A[N]; vector<int> B; long long Pref[N]; int Prev[N]; int Dp[N]; void init() { cin >> n; bool negative = 0; B.push_back(0); for (int i=1; i<=n; i++) { cin >> A[i]; Pref[i] = Pref[i-1] + A[i]; if (A[i] != 0) { B.push_back(i); } if (A[i] < 0) { negative = 1; } if (negative == 1) { Dp[i] = N; } if (A[i-1] != 0) { Prev[i] = i - 1; } else { Prev[i] = Prev[i-1]; } } } void solve() { int last = -1; for (int i=1; i<B.size(); i++) { if (A[B[i]] < 0) { for (int j=1; j<i; j++) { if (Pref[B[i]] - Pref[B[j]-1] >= 0) { Dp[B[i]] = min(Dp[B[i]], B[i] - B[j] + Dp[Prev[B[j]]]); } } last = i; } if (A[B[i]] > 0 && Dp[B[i]] > 0) { for (int j=1; j<=last; j++) { if (Pref[B[i]] - Pref[B[j]-1] >= 0) { Dp[B[i]] = min(min(Dp[B[i]], Dp[B[i-1]]), B[i] - B[j] + Dp[Prev[B[j]]]); } } } } /* for (int i=0; i<B.size(); i++) { cout << Dp[B[i]] << ' '; } cout << '\n'; */ int mini = N; for (int i=B.size()-1; i>=0; i--) { mini = min(mini, Dp[B[i]]); if (A[B[i]] < 0) { break; } } if (Pref[n] < 0) { cout << "-1\n"; } else { cout << mini << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); init(); solve(); return 0; } |