#include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; struct ef { int x; int e; }; vector<ef> dat; map<pair<int,int>,int> cache; int rec(int k, int e) { auto q = pair<int,int>(k, e); if (cache.find(q) != cache.end()) return cache[q]; int b = e+dat[k].e; if (k == dat.size()-1 && b >= 0) return 0; if (k == dat.size()-1 && b < 0) return -1; int n = k+1; int d = dat[n].x - dat[k].x; int res = 0; if (b == 0) { res = rec(n, 0); } else if (b < 0) { int y = rec(n, b); res = y >= 0 ? y+d : -1; } else { int y = rec(n, b); // cout << b << " " << y << "\n"; if (y == -1) res = -1; else { int f2 = rec(n, 0); if (f2 == -1 ) res = y+d; else res = min(y+d, f2); } } cache[q] = res; return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; long long bilans = 0; dat.reserve(n); int f = 0; for (int i=0;i<n;i++) { int p; cin >> p; if (p != 0) { ef pos; pos.x = i; pos.e = p; dat.push_back(pos); } if (p < 0) f++; bilans += p; } // for (auto &x : dat) { // cout << x.e << " x=" << x.x << "\n"; // } if (f == 0) { // trywialny przypadek - nie mamy fabryk, nic nie trzeba laczyc cout << "0\n"; return 0; } if (bilans < 0) { // trywialny przypadek - wieksze zuzycie niz produkcja, nie da sie cout << "-1\n"; return 0; } int res = rec(0, 0); cout << res << '\n'; 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 | #include <iostream> #include <vector> #include <algorithm> #include <map> using namespace std; struct ef { int x; int e; }; vector<ef> dat; map<pair<int,int>,int> cache; int rec(int k, int e) { auto q = pair<int,int>(k, e); if (cache.find(q) != cache.end()) return cache[q]; int b = e+dat[k].e; if (k == dat.size()-1 && b >= 0) return 0; if (k == dat.size()-1 && b < 0) return -1; int n = k+1; int d = dat[n].x - dat[k].x; int res = 0; if (b == 0) { res = rec(n, 0); } else if (b < 0) { int y = rec(n, b); res = y >= 0 ? y+d : -1; } else { int y = rec(n, b); // cout << b << " " << y << "\n"; if (y == -1) res = -1; else { int f2 = rec(n, 0); if (f2 == -1 ) res = y+d; else res = min(y+d, f2); } } cache[q] = res; return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; long long bilans = 0; dat.reserve(n); int f = 0; for (int i=0;i<n;i++) { int p; cin >> p; if (p != 0) { ef pos; pos.x = i; pos.e = p; dat.push_back(pos); } if (p < 0) f++; bilans += p; } // for (auto &x : dat) { // cout << x.e << " x=" << x.x << "\n"; // } if (f == 0) { // trywialny przypadek - nie mamy fabryk, nic nie trzeba laczyc cout << "0\n"; return 0; } if (bilans < 0) { // trywialny przypadek - wieksze zuzycie niz produkcja, nie da sie cout << "-1\n"; return 0; } int res = rec(0, 0); cout << res << '\n'; return 0; } |