#include <vector> #include <iostream> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; int main() { std::ios::sync_with_stdio(false); int n, m; cin >> n; vector<ll> cash(n); for (int i = 0; i < n; ++i) cin >> cash[i]; cin >> m; string s; cin >> s; vector<ll> next(m, -1); vector<ll> balance(m); vector<ll> minNegative(m); int cycleLen = 0; for (int i = 0; i < m; ++i) { if (next[i] == -1) { ll localCycleLen = 0; ll localBalance = 0; ll localMinNegative = 0; int pos = i; do { localBalance += (s[pos] == 'W' ? 1 : -1); next[pos] = (pos+n)%m; pos = (pos+n)%m; localCycleLen++; localMinNegative = min(localMinNegative, localBalance); } while (next[pos] == -1); int tmp = i; for (int j = 0; j < localCycleLen; ++j) { balance[tmp] = localBalance; tmp = (tmp+n)%m; } minNegative[i] = localMinNegative; cycleLen = localCycleLen; } if (false) { // this makes algorithm O(m^2) it needs improvement ll localBalance = 0; ll localMin = 0; ll pos = i; for (int i = 0; i < cycleLen; ++i) { localBalance += (s[pos] == 'W' ? 1 : -1); pos = (pos+n)%m; localMin = min(localMin, localBalance); } minNegative[i] = localMin; } } /* for (auto e : next) cout << e << " "; cout << endl; for (auto e : balance) cout << e << " "; cout << endl; for (auto e : minNegative) cout << e << " "; cout << endl; */ ll minFullCycles = 2e6; bool forever = true; for (int i = 0; i < n; ++i) { if (balance[i%m] < 0 || cash[i] <= minNegative[i%m]) { forever = false; break; } } if (forever) { cout << -1 << endl; return 0; } ll result = 0; ll nIdx = 0; ll mIdx = 0; while (true) { result++; cash[nIdx] += s[mIdx] == 'W' ? 1 : -1; if (cash[nIdx] == 0) break; nIdx = (nIdx+1)%n; mIdx = (mIdx+1)%m; } cout << result << 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 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 107 | #include <vector> #include <iostream> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; int main() { std::ios::sync_with_stdio(false); int n, m; cin >> n; vector<ll> cash(n); for (int i = 0; i < n; ++i) cin >> cash[i]; cin >> m; string s; cin >> s; vector<ll> next(m, -1); vector<ll> balance(m); vector<ll> minNegative(m); int cycleLen = 0; for (int i = 0; i < m; ++i) { if (next[i] == -1) { ll localCycleLen = 0; ll localBalance = 0; ll localMinNegative = 0; int pos = i; do { localBalance += (s[pos] == 'W' ? 1 : -1); next[pos] = (pos+n)%m; pos = (pos+n)%m; localCycleLen++; localMinNegative = min(localMinNegative, localBalance); } while (next[pos] == -1); int tmp = i; for (int j = 0; j < localCycleLen; ++j) { balance[tmp] = localBalance; tmp = (tmp+n)%m; } minNegative[i] = localMinNegative; cycleLen = localCycleLen; } if (false) { // this makes algorithm O(m^2) it needs improvement ll localBalance = 0; ll localMin = 0; ll pos = i; for (int i = 0; i < cycleLen; ++i) { localBalance += (s[pos] == 'W' ? 1 : -1); pos = (pos+n)%m; localMin = min(localMin, localBalance); } minNegative[i] = localMin; } } /* for (auto e : next) cout << e << " "; cout << endl; for (auto e : balance) cout << e << " "; cout << endl; for (auto e : minNegative) cout << e << " "; cout << endl; */ ll minFullCycles = 2e6; bool forever = true; for (int i = 0; i < n; ++i) { if (balance[i%m] < 0 || cash[i] <= minNegative[i%m]) { forever = false; break; } } if (forever) { cout << -1 << endl; return 0; } ll result = 0; ll nIdx = 0; ll mIdx = 0; while (true) { result++; cash[nIdx] += s[mIdx] == 'W' ? 1 : -1; if (cash[nIdx] == 0) break; nIdx = (nIdx+1)%n; mIdx = (mIdx+1)%m; } cout << result << endl; } |