#include <bits/stdc++.h> using namespace std; const int N = 1000005, C = 2000000; int n, m; long long money[N]; char state[N]; bool vis[N]; vector<long long> start[N]; struct Queue { vector<int>v; int poc = 0; void push(int w) { v.push_back(w); } void pop() { poc++; } int front() { return v[poc]; } bool empty() { return poc >= v.size(); } int size() { return v.size() - poc; } }; Queue Q[4 * N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld", &money[i]); } scanf("%d", &m); scanf("%s", state); for (int i = 0; i < m; i++) { state[i] = (state[i] == 'W'? 1: -1); } for (int i = 0; i < n; i++) { start[i % m].push_back(i); } long long ans = 2e18; for (int i = 0; i < m; i++) { if (vis[i]) { continue; } long long endPosition = 0; long long endPrefSum = 0; long long mini = 0; int w = i; Q[C].push(0); do { endPrefSum += state[w]; Q[endPrefSum + C].push(++endPosition); mini = min(mini, endPrefSum); w = (w + n) % m; } while (w != i); long long beginPrefSum = 0; long long beginPosition = 0; do { vis[w] = true; for (int j = 0; j < start[w].size(); j++) { long long currentMoney = money[start[w][j]]; if (currentMoney <= -(mini - beginPrefSum)) { long long numberOfSteps = Q[-currentMoney + beginPrefSum + C].front() - beginPosition; ans = min(ans, start[w][j] + 1 + (long long)(numberOfSteps - 1) * n); } else if (endPrefSum - beginPrefSum >= 0) { continue; } else { long long newValue = currentMoney + (mini - beginPrefSum); long long numberOfCycles = (newValue + beginPrefSum - endPrefSum - 1) / (beginPrefSum - endPrefSum); long long totalDistance = start[w][j] + 1 + numberOfCycles * (endPosition - beginPosition) * n; currentMoney += (long long)(endPrefSum - beginPrefSum) * numberOfCycles; long long numberOfSteps = Q[-currentMoney + beginPrefSum + C].front() - beginPosition; ans = min(ans, totalDistance + (long long)(numberOfSteps - 1) * n); } } beginPosition++; endPosition++; Q[beginPrefSum + C].pop(); if (beginPrefSum == mini && Q[beginPrefSum + C].empty()) { mini++; } beginPrefSum += state[w]; endPrefSum += state[w]; Q[endPrefSum + C].push(endPosition); if (endPrefSum < mini) { mini = endPrefSum; } w = (w + n) % m; } while(w != i); do { Q[beginPrefSum + C].pop(); beginPrefSum += state[w]; w = (w + n) % m; } while(w != i); Q[beginPrefSum + C].pop(); } if (ans == 2e18) { printf("-1\n"); } else { printf("%lld\n", ans); } 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 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | #include <bits/stdc++.h> using namespace std; const int N = 1000005, C = 2000000; int n, m; long long money[N]; char state[N]; bool vis[N]; vector<long long> start[N]; struct Queue { vector<int>v; int poc = 0; void push(int w) { v.push_back(w); } void pop() { poc++; } int front() { return v[poc]; } bool empty() { return poc >= v.size(); } int size() { return v.size() - poc; } }; Queue Q[4 * N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%lld", &money[i]); } scanf("%d", &m); scanf("%s", state); for (int i = 0; i < m; i++) { state[i] = (state[i] == 'W'? 1: -1); } for (int i = 0; i < n; i++) { start[i % m].push_back(i); } long long ans = 2e18; for (int i = 0; i < m; i++) { if (vis[i]) { continue; } long long endPosition = 0; long long endPrefSum = 0; long long mini = 0; int w = i; Q[C].push(0); do { endPrefSum += state[w]; Q[endPrefSum + C].push(++endPosition); mini = min(mini, endPrefSum); w = (w + n) % m; } while (w != i); long long beginPrefSum = 0; long long beginPosition = 0; do { vis[w] = true; for (int j = 0; j < start[w].size(); j++) { long long currentMoney = money[start[w][j]]; if (currentMoney <= -(mini - beginPrefSum)) { long long numberOfSteps = Q[-currentMoney + beginPrefSum + C].front() - beginPosition; ans = min(ans, start[w][j] + 1 + (long long)(numberOfSteps - 1) * n); } else if (endPrefSum - beginPrefSum >= 0) { continue; } else { long long newValue = currentMoney + (mini - beginPrefSum); long long numberOfCycles = (newValue + beginPrefSum - endPrefSum - 1) / (beginPrefSum - endPrefSum); long long totalDistance = start[w][j] + 1 + numberOfCycles * (endPosition - beginPosition) * n; currentMoney += (long long)(endPrefSum - beginPrefSum) * numberOfCycles; long long numberOfSteps = Q[-currentMoney + beginPrefSum + C].front() - beginPosition; ans = min(ans, totalDistance + (long long)(numberOfSteps - 1) * n); } } beginPosition++; endPosition++; Q[beginPrefSum + C].pop(); if (beginPrefSum == mini && Q[beginPrefSum + C].empty()) { mini++; } beginPrefSum += state[w]; endPrefSum += state[w]; Q[endPrefSum + C].push(endPosition); if (endPrefSum < mini) { mini = endPrefSum; } w = (w + n) % m; } while(w != i); do { Q[beginPrefSum + C].pop(); beginPrefSum += state[w]; w = (w + n) % m; } while(w != i); Q[beginPrefSum + C].pop(); } if (ans == 2e18) { printf("-1\n"); } else { printf("%lld\n", ans); } return 0; } |