#include <cstdio> #include <utility> using namespace std; pair <int, long long> a[41][1000001]; int wl[1000001], hajs[1000001]; int m, beg; char wq; long long tab[41], wyn, bes = 1000000000, pom, n, p; int main() { tab[0] = 1; bes *= bes; p = bes; for (int i = 1; i <= 40; i++) tab[i] = 2*tab[i-1]; scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%d", &hajs[i]); scanf("%d", &m); for (int i = 1; i <= m; i++) { scanf(" %c", &wq); if (wq == 'W') wl[i] = 1; else wl[i] = -1; } for (int i = 1; i <= m; i++) a[0][i] = make_pair(0,wl[i]); for (int i = 1; i <= 40; i++) { for (int j = 1; j <= m; j++) { pom = (j+tab[i-1]*n-1)%m+1; a[i][j].second = a[i-1][j].second; a[i][j].second += a[i-1][pom].second; a[i][j].first = a[i-1][j].first; if (a[i-1][j].second+a[i-1][pom].first < -1000001) a[i][j].first = -1000001; else { if(a[i-1][j].second+a[i-1][pom].first < a[i][j].first) a[i][j].first = a[i-1][j].second+a[i-1][pom].first; } } } /* for (int i = 1; i <= m; i++) { printf("%d:", i); for (int j = 0; j <= 40; j++) { printf("%d %lld; ", a[j][i].first, a[j][i].second); } printf("\n"); }*/ for (int i = 1; i <= n; i++) { wyn = 0; beg = i%m; if (a[40][beg].first + hajs[i] > 0) continue; for (int j = 40; j >= 0; j--) { if (hajs[i] + a[j][beg].first > 0) { wyn += tab[j]; if ((wyn-1)*n+i > bes) continue; hajs[i] += a[j][beg].second; beg = (beg+tab[j]*n-1)%m+1; } } wyn = (wyn-1)*n+i; if (wyn < bes) bes = wyn; } if (bes == p) { printf("-1"); return 0; } printf("%lld", bes); 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 | #include <cstdio> #include <utility> using namespace std; pair <int, long long> a[41][1000001]; int wl[1000001], hajs[1000001]; int m, beg; char wq; long long tab[41], wyn, bes = 1000000000, pom, n, p; int main() { tab[0] = 1; bes *= bes; p = bes; for (int i = 1; i <= 40; i++) tab[i] = 2*tab[i-1]; scanf("%lld", &n); for (int i = 1; i <= n; i++) scanf("%d", &hajs[i]); scanf("%d", &m); for (int i = 1; i <= m; i++) { scanf(" %c", &wq); if (wq == 'W') wl[i] = 1; else wl[i] = -1; } for (int i = 1; i <= m; i++) a[0][i] = make_pair(0,wl[i]); for (int i = 1; i <= 40; i++) { for (int j = 1; j <= m; j++) { pom = (j+tab[i-1]*n-1)%m+1; a[i][j].second = a[i-1][j].second; a[i][j].second += a[i-1][pom].second; a[i][j].first = a[i-1][j].first; if (a[i-1][j].second+a[i-1][pom].first < -1000001) a[i][j].first = -1000001; else { if(a[i-1][j].second+a[i-1][pom].first < a[i][j].first) a[i][j].first = a[i-1][j].second+a[i-1][pom].first; } } } /* for (int i = 1; i <= m; i++) { printf("%d:", i); for (int j = 0; j <= 40; j++) { printf("%d %lld; ", a[j][i].first, a[j][i].second); } printf("\n"); }*/ for (int i = 1; i <= n; i++) { wyn = 0; beg = i%m; if (a[40][beg].first + hajs[i] > 0) continue; for (int j = 40; j >= 0; j--) { if (hajs[i] + a[j][beg].first > 0) { wyn += tab[j]; if ((wyn-1)*n+i > bes) continue; hajs[i] += a[j][beg].second; beg = (beg+tab[j]*n-1)%m+1; } } wyn = (wyn-1)*n+i; if (wyn < bes) bes = wyn; } if (bes == p) { printf("-1"); return 0; } printf("%lld", bes); return 0; } |