// Artur Kraska, II UWr #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <list> #include <set> #include <map> #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #define FOR(i, a, b) for(int i=a; i<=b; i++) #define FORD(i, a, b) for(int i=a; i>=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 2000007 #define INF 1000000000000000007ll #define g(nr) gdzie[nr+M] using namespace std; int n, m, tab[1000007]; char slowo[1000007]; int gdzie[4000017]; int t[1000007]; long long poz, wys, minn, diff, ile; long long res_minn = INF; bool byl[1000007]; int kto[1000007]; void generuj(int nr) { poz = 0; ile = 0; minn = 0; wys = 0; diff = 0; for(int i = nr; !byl[i]; i = (i+n)%m) { // cout << " wchodzi do " << i << endl; byl[i] = 1; kto[ile] = i; t[ile] = (slowo[i] == 'W' ? 1 : -1); diff += t[ile]; ile++; } FORD(i, ile-1, 0) { wys -= t[i]; g(wys) = --poz; minn = min(minn, wys); // cout << "g[" << wys << "] = " << g(wys) << endl; } } void zliczaj(int nr) { long long res = 0; long long kasa = tab[nr]; // cout << " diff: " << diff << ", minn: " << minn << ", kasa: " << kasa << endl; long long wys2 = wys - minn; if(kasa > wys2) { if(diff >= 0) return ; long long ill = (kasa-wys2-diff-1)/(-diff); res = ill*ile; kasa -= ill*(-diff); } res += g(wys-kasa) - poz; // cout << " gosc " << nr << " odpadnie po " << res << " kolejkach" << endl; res_minn = min(res_minn, (res-1)*n+nr+1); } void dzialaj(int nr) { FORD(i, ile-1, 0) { wys -= t[i]; g(wys) = --poz; minn = min(minn, wys); // cout << "g[" << wys << "] = " << g(wys) << endl; // cout << "poz: " << poz << ", wys: " << wys << ", minn: " << minn << endl; for(int j=kto[i]; j < n; j += m) zliczaj(j); } } int main() { scanf("%d", &n); forr(i, n) scanf("%d", &tab[i]); scanf("%d", &m); scanf("%s", slowo); forr(i, m) { if(byl[i]) continue; generuj(i); dzialaj(i); } if(res_minn == INF) printf("-1\n"); else printf("%lld\n", res_minn); 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 124 125 | // Artur Kraska, II UWr #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <list> #include <set> #include <map> #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #define FOR(i, a, b) for(int i=a; i<=b; i++) #define FORD(i, a, b) for(int i=a; i>=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 2000007 #define INF 1000000000000000007ll #define g(nr) gdzie[nr+M] using namespace std; int n, m, tab[1000007]; char slowo[1000007]; int gdzie[4000017]; int t[1000007]; long long poz, wys, minn, diff, ile; long long res_minn = INF; bool byl[1000007]; int kto[1000007]; void generuj(int nr) { poz = 0; ile = 0; minn = 0; wys = 0; diff = 0; for(int i = nr; !byl[i]; i = (i+n)%m) { // cout << " wchodzi do " << i << endl; byl[i] = 1; kto[ile] = i; t[ile] = (slowo[i] == 'W' ? 1 : -1); diff += t[ile]; ile++; } FORD(i, ile-1, 0) { wys -= t[i]; g(wys) = --poz; minn = min(minn, wys); // cout << "g[" << wys << "] = " << g(wys) << endl; } } void zliczaj(int nr) { long long res = 0; long long kasa = tab[nr]; // cout << " diff: " << diff << ", minn: " << minn << ", kasa: " << kasa << endl; long long wys2 = wys - minn; if(kasa > wys2) { if(diff >= 0) return ; long long ill = (kasa-wys2-diff-1)/(-diff); res = ill*ile; kasa -= ill*(-diff); } res += g(wys-kasa) - poz; // cout << " gosc " << nr << " odpadnie po " << res << " kolejkach" << endl; res_minn = min(res_minn, (res-1)*n+nr+1); } void dzialaj(int nr) { FORD(i, ile-1, 0) { wys -= t[i]; g(wys) = --poz; minn = min(minn, wys); // cout << "g[" << wys << "] = " << g(wys) << endl; // cout << "poz: " << poz << ", wys: " << wys << ", minn: " << minn << endl; for(int j=kto[i]; j < n; j += m) zliczaj(j); } } int main() { scanf("%d", &n); forr(i, n) scanf("%d", &tab[i]); scanf("%d", &m); scanf("%s", slowo); forr(i, m) { if(byl[i]) continue; generuj(i); dzialaj(i); } if(res_minn == INF) printf("-1\n"); else printf("%lld\n", res_minn); return 0; } |