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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>

template<typename T>
void dump(const std::vector<T> &vec) {
    for (int i = 0; i < (int)vec.size(); ++i) {
        printf("%d%c", (int)vec[i], " \n"[i == (int)vec.size() - 1]);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    std::vector<long long> funds(n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &funds[i]);
    }
    //printf("Funds: ");
    //dump(funds);
    int m;
    scanf("%d", &m);
    std::string cycle;
    std::cin >> cycle;
    //printf("Cycle: %s\n", cycle.c_str());
    std::vector<int> low(m ,0);
    std::vector<int> tot(m, 0);
    std::vector<bool> vis(m, false);
    //printf("Calc\n");
    int lowCycles = 0;
    for (int i = 0; i < m; ++i) {
        if (!vis[i]) {
            int lowest = 1000009;
            int prev = 0;
            int pos = i;
            do {
                vis[pos] = true;
                prev += cycle[pos] == 'W' ? 1 : -1;
                if (prev < lowest)
                    lowest = prev;
                pos += n;
                pos %= cycle.length();
            } while (pos != i);
            pos = i;
            if (prev < 0)
                lowCycles += 1;
            do {
                low[pos] = lowest;
                tot[pos] = prev;
                pos += n;
                pos %= cycle.length();
            } while (pos != i);
        }
    }
    //printf("Low: ");
    //dump(low);
    //printf("Tot: ");
    //dump(tot);

    long long rounds = 0;
    bool foundLow = false;

    int need = 1000009;
    for (int i = 0; i < n; ++i) {
        if (funds[i] + low[i % m] <= 0) {
            need = 1;
            foundLow = true;
            break;
        } else {
            if (tot[i % m] < 0) {
                int tmp = (funds[i] + low[i % m]) / (-tot[i % m]);
                if (tmp >= 0 && tmp < need)
                    need = tmp + 1;
            }
        }
    }
    if (!foundLow && lowCycles == 0) {
        printf("-1\n");
    } else {
        //printf("Need: %d\n", need);

        rounds += (need - 1) * n;

        if (need > 1) {
            for (int i = 0; i < n; ++i) {
                funds[i] += tot[i % m] * (need - 1);
            }
            need = 1;
        }

        //printf("New funds: ");
        //dump(funds);

        int high = 0;
        std::vector<int> start(m, -1);
        for (int i = 0; i < m; ++i) {
            if (start[i] == -1) {
                high = i;
                int pos = i;
                do {
                    start[pos] = i;
                    pos += n;
                    pos %= m;
                } while (pos != i);
            }
        }
        //printf("Start: ");
        //dump(start);
        std::vector<long long> look(high + 1, -1000009);
        std::vector<int> pos(high + 1, -1);
        for (int i = 0; i < n; ++i) {
            if (-funds[i] > look[start[i % m]]) {
                pos[start[i % m]] = i;
                look[start[i % m]] = -funds[i];
            }
        }

        //printf("Look: ");
        //dump(look);

        //printf("Pos: ");
        //dump(pos);

        vis.clear();
        vis.resize(m, false);

        int lowest = 1000009;

        for (int i = 0; i < m; ++i) {
            if (!vis[i]) {
                int prev = 0;
                int poscyc = i % m;
                int len = 0;
                do {
                    vis[poscyc] = true;
                    prev += cycle[poscyc] == 'W' ? 1 : -1;
                    if (prev == look[start[i]]) {
                        int tmp = len * n + pos[start[i]] + 1;
                        if (tmp < lowest)
                            lowest = tmp;
                        break;
                    }
                    poscyc += n;
                    poscyc %= m;
                    ++len;
                } while (poscyc != i);
            }
        }
        //printf("Lowest: %d\nRounds: %lld\n", lowest, rounds);
        printf("%lld\n", rounds + lowest);
    }
}