#include <cstdio> #define N 500000 + 10 long long int a[N]; long long int s1[N]; long long int cache[N]; long long int suma(int a, int b) { return s1[b] - s1[a - 1]; } void aktualizuj_cache(long long int modyfikator, int from, long long int result) { if (modyfikator == 0) { cache[from] = result; } } long long int oblicz(int from, int to, long long int modyfikator) { if (from > to) { return -1L; } if (modyfikator == 0L && cache[from] != -2L) { return cache[from]; } if (suma(from, to) + modyfikator < 0L) { long long int result = -1L; aktualizuj_cache(modyfikator, from, result); return result; } if (from == to) { if (suma(from, to) + modyfikator >= 0L) { long long int result = 0L; aktualizuj_cache(modyfikator, from, result); return result; } else { long long int result = -1L; aktualizuj_cache(modyfikator, from, result); return result; } } if (a[from] + modyfikator == 0L) { long long int result = oblicz(from + 1, to, 0L); aktualizuj_cache(modyfikator, from, result); return result; } else if (a[from] + modyfikator < 0L) { long long int result = oblicz(from + 1, to, a[from] + modyfikator) + 1L; aktualizuj_cache(modyfikator, from, result); return result; } else { long long int z = oblicz(from + 1, to, a[from] + modyfikator) + 1L; long long int bez = oblicz(from + 1, to, 0L); if (z == -1L && bez == -1L) { long long int result = -1L; aktualizuj_cache(modyfikator, from, result); return result; } if (bez == -1L) { long long int result = z; aktualizuj_cache(modyfikator, from, result); return result; } if (z == -1L) { long long int result = bez; aktualizuj_cache(modyfikator, from, result); return result; } long long int result = z < bez ? z : bez; aktualizuj_cache(modyfikator, from, result); return result; } } int main() { int n; scanf("%d", &n); for (int i = 0; i < N; i++) { cache[i] = -2L; } for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } for (int i = 1; i <= n; i++) { s1[i] = s1[i - 1] + a[i]; } printf("%lld", oblicz(1, n, 0L)); 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 105 106 | #include <cstdio> #define N 500000 + 10 long long int a[N]; long long int s1[N]; long long int cache[N]; long long int suma(int a, int b) { return s1[b] - s1[a - 1]; } void aktualizuj_cache(long long int modyfikator, int from, long long int result) { if (modyfikator == 0) { cache[from] = result; } } long long int oblicz(int from, int to, long long int modyfikator) { if (from > to) { return -1L; } if (modyfikator == 0L && cache[from] != -2L) { return cache[from]; } if (suma(from, to) + modyfikator < 0L) { long long int result = -1L; aktualizuj_cache(modyfikator, from, result); return result; } if (from == to) { if (suma(from, to) + modyfikator >= 0L) { long long int result = 0L; aktualizuj_cache(modyfikator, from, result); return result; } else { long long int result = -1L; aktualizuj_cache(modyfikator, from, result); return result; } } if (a[from] + modyfikator == 0L) { long long int result = oblicz(from + 1, to, 0L); aktualizuj_cache(modyfikator, from, result); return result; } else if (a[from] + modyfikator < 0L) { long long int result = oblicz(from + 1, to, a[from] + modyfikator) + 1L; aktualizuj_cache(modyfikator, from, result); return result; } else { long long int z = oblicz(from + 1, to, a[from] + modyfikator) + 1L; long long int bez = oblicz(from + 1, to, 0L); if (z == -1L && bez == -1L) { long long int result = -1L; aktualizuj_cache(modyfikator, from, result); return result; } if (bez == -1L) { long long int result = z; aktualizuj_cache(modyfikator, from, result); return result; } if (z == -1L) { long long int result = bez; aktualizuj_cache(modyfikator, from, result); return result; } long long int result = z < bez ? z : bez; aktualizuj_cache(modyfikator, from, result); return result; } } int main() { int n; scanf("%d", &n); for (int i = 0; i < N; i++) { cache[i] = -2L; } for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } for (int i = 1; i <= n; i++) { s1[i] = s1[i - 1] + a[i]; } printf("%lld", oblicz(1, n, 0L)); return 0; } |