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
#include <iostream>
using namespace std;
const long long MAXN = 1000000;
long long kolega[MAXN], cykl[MAXN], cyklSuma[MAXN], cyklMin[MAXN], ktory[MAXN];
char napis[MAXN];
long long nwd(long long a, long long b) {
    if(b!=0)
      return nwd(b,a%b);
    return a;
}

long long maxWObrocie(long long n, long long m, long long i, long long d) {
    if (i % m < m / d)
        return cyklMin[(i + n * (m / d - 1)) % m];
    long long wynik1 = cyklMin[(i + n * (m / d - 1)) % m] - cyklSuma[(i + m - (n%m)) % m];
    long long wynik2 = cyklSuma[(i + n * (m / d - 1)) % m] + cyklMin[(i + m - (n%m)) % m];
    if (wynik1 < wynik2)
        return wynik1;
    return wynik2;
}

long long ileWObrocie(long long n, long long m, long long i, long long d) {
    return cyklSuma[(i % d + n * (m / d - 1)) % m];
}

long long maxWIndeks(long long n, long long m, long long i, long long indeks, long long d) {
    if (ktory[i] == 0)
        return cyklMin[(i + indeks * n) % m];
    if (m / d  > ktory[i] + indeks)
        return cyklMin[(i + indeks * n) % m] - cyklSuma[(i - (n%m) + m) % m];
    return cyklMin[(i + indeks * n) % m] - cyklSuma[(i - (n%m) + m) % m] + cyklSuma[(i % d + n * (m / d - 1)) % m];

}



int main() {
    ios_base::sync_with_stdio(0);
    long long n, m;
    cin>>n;
    for (long long i = 0; i < n; i++) {
        cin >> kolega[i];
    }
    cin >> m;
    cin >> napis;
    long long d = nwd (m, n);
    for (long long i = 0; i < d; i++) {
        bool start = false;
        long long ktr = 0;
        for (long long j = i; j != i || !start; j = (j + n) % m) {
            ktory[j] = ktr;
            ktr++;
            start = true;
            if (napis[j] == 'W')
                cykl[j] = 1;
            else if (napis[j] == 'P')
                cykl[j] = -1;
            else {
                cout << "BLAD\n";
                return 0;
            }
            cyklSuma[j] = cykl[j];
            if (j != i)
                cyklSuma[j] += cyklSuma[(j - (n%m) + m) % m];
            cyklMin[j] = cyklSuma[j];
            if (j != i && cyklMin[j] > cyklMin[(j - (n%m) + m) % m])
                cyklMin[j] = cyklMin[(j - (n%m) + m) % m];
            }
    }
    long long pierwszy = 2 * MAXN * MAXN * MAXN;
    long long bankrut;
    for (long long i = 0; i < n; i++) {
        bankrut = i + 1;
        long long maxMinus = maxWObrocie(n, m, i, d);
        long long obrotMinus = ileWObrocie(n, m, i, d);
        //cout << "maxminus " << maxMinus << " obrotminus " << obrotMinus << '\n';
        if (maxMinus >= 0)
            continue;
        if (-maxMinus < kolega[i]) {
            if (obrotMinus >= 0)
                continue;
            bankrut += (kolega[i] + maxMinus) / (-obrotMinus) * n * m / d;
            kolega[i] -= (kolega[i] + maxMinus) % (-obrotMinus) - maxMinus;
            //cout << bankrut << '\n';
        }
        if (kolega[i] > -maxMinus) {
            kolega[i] += obrotMinus;
            bankrut += n * m / d;
        }

        long long lewy = 0;
        long long prawy = m / d;
        long long srodek;
        while (lewy < prawy) {
            srodek = (lewy + prawy) / 2;
            if ( -maxWIndeks(n, m, i, srodek, d) < kolega[i])
                lewy = srodek + 1;
            else
                prawy = srodek;
        }
        bankrut += n * lewy;
        //cout << "lewy = " << lewy << '\n';
        //cout << "bankrut" << bankrut << '\n';
        if (bankrut < pierwszy)
            pierwszy = bankrut;
    }
    if (pierwszy == 2 * MAXN * MAXN * MAXN)
        cout << "-1\n";
    else
        cout << pierwszy << '\n';
}