#include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long ll; const ll inf = 2e18; char s[1000001]; int k[1000000]; int v[1000000]; bool vis[1000000]; int main() { int n, m; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", k + i); scanf("%d %s", &m, s); for(int i = 0; i < m; i++) v[i] = s[i] == 'W' ? 1 : -1; ll ans = inf; for(int i = 0; i < m; i++) { if(vis[i]) continue; int sum = 0, mn = 0; ll t = 0; priority_queue<pair<int, ll> > pq; for(int j = i; !vis[j]; j = (j + n) % m) { vis[j] = true; t++; for(int l = j; l < n; l += m) pq.push(make_pair(sum - k[l], (ll)t * n - (l + 1))); sum += v[j]; mn = min(mn, sum); while(!pq.empty() && pq.top().first == sum) { auto p = pq.top(); pq.pop(); ans = min(ans, (ll)t * n - p.second); } } int ct = t, csum = sum; if(!pq.empty() && csum < 0) { int pelne = max(0, (sum + mn - pq.top().first) / (-csum)); sum += pelne * csum; t += (ll)pelne * ct; } for(int T = 0, j = i; T <= 3 * ct && !pq.empty(); T++, j = (j + n) % m) { while(!pq.empty() && pq.top().first == sum) { auto p = pq.top(); pq.pop(); ans = min(ans, (ll)t * n - p.second); } t++; sum += v[j]; } } if(ans == inf) puts("-1"); else printf("%lld\n", ans); }
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 | #include <cstdio> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long ll; const ll inf = 2e18; char s[1000001]; int k[1000000]; int v[1000000]; bool vis[1000000]; int main() { int n, m; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", k + i); scanf("%d %s", &m, s); for(int i = 0; i < m; i++) v[i] = s[i] == 'W' ? 1 : -1; ll ans = inf; for(int i = 0; i < m; i++) { if(vis[i]) continue; int sum = 0, mn = 0; ll t = 0; priority_queue<pair<int, ll> > pq; for(int j = i; !vis[j]; j = (j + n) % m) { vis[j] = true; t++; for(int l = j; l < n; l += m) pq.push(make_pair(sum - k[l], (ll)t * n - (l + 1))); sum += v[j]; mn = min(mn, sum); while(!pq.empty() && pq.top().first == sum) { auto p = pq.top(); pq.pop(); ans = min(ans, (ll)t * n - p.second); } } int ct = t, csum = sum; if(!pq.empty() && csum < 0) { int pelne = max(0, (sum + mn - pq.top().first) / (-csum)); sum += pelne * csum; t += (ll)pelne * ct; } for(int T = 0, j = i; T <= 3 * ct && !pq.empty(); T++, j = (j + n) % m) { while(!pq.empty() && pq.top().first == sum) { auto p = pq.top(); pq.pop(); ans = min(ans, (ll)t * n - p.second); } t++; sum += v[j]; } } if(ans == inf) puts("-1"); else printf("%lld\n", ans); } |