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;
}