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
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;


int find_first(vector<int> &arr, int val) {
    for(int i = 0; i < arr.size(); ++i) {
        if(arr[i] == val) {
            return i;
        }
    }
    return -1;
}


int main() {
    int n, m;
    LL min_games = LLONG_MAX;
    scanf("%d", &n);
    vector<int> savings;
    savings.resize(n);
    for(int i = 0; i < n; ++i) {
        int ss;
        scanf("%d", &ss);
        savings[i] = ss;
    }
    scanf("%d", &m);
    char scycle[1000000 + 1];
    scanf("%s", scycle);

    if(m == 1) {
        for(int i = 0; i < n; ++i) {
            min_games = min(min_games, i + 1LL + n * (savings[i] - 1));
        }
        printf("%lld\n", min_games);
        return 0;
    }

    vector<int> cycle;
    cycle.resize(m);
    for(int i = 0; i < m; ++i) {
        if(scycle[i] == 'W') {
            cycle[i] = 1;
        } else {
            cycle[i] = -1;
        }
    }
    int starting_cycles = min(m, n);
    bool found = false;
    for(int c = 0; c < starting_cycles; ++c) {
        int start = c, curr = c;
        vector<int> partial_sum;
        int sum = 0, max_down = 0;
        while(true) {
            sum += cycle[curr];
            max_down = min(max_down, sum);
            partial_sum.push_back(sum);
            
            curr = (curr + n) % m;
            if(curr == start) {
                break;
            }
        }
        /*
        printf("cycle: ");
        for(int i = 0; i < partial_sum.size(); ++i) printf("%d ", partial_sum[i]);
        printf("\n");
        */
        for(int boy = c; boy < n; boy += m) {
            //printf("boy %d savings=%d\n", boy, savings[boy]);
            if(savings[boy] + max_down <= 0 || sum < 0) {
                int after_max_down = savings[boy] + max_down;
                if(after_max_down <= 0) {
                    int psi = find_first(partial_sum, -savings[boy]);
                    LL local_min = boy + 1 + n * psi;
                    min_games = min(min_games, local_min);
                    found = true;
                    /*
                    printf("that was quick: local=%lld ming=%lld\n", local_min, min_games);
                    printf("\n");
                    */
                    continue;
                }
                int quot = after_max_down / sum;
                if(quot * sum < after_max_down) {
                    --quot;
                }
                int down = savings[boy] - quot * sum;
                int part_cycle = find_first(partial_sum, -down);
                found = true;
                int full_cycles = abs(quot);
                LL local_min = (LL)full_cycles * partial_sum.size() * n + part_cycle * n + boy + 1;
                min_games = min(min_games, local_min);
                /*
                printf("that took longer: local=%lld ming=%lld\n", local_min, min_games);
                printf("full=%d partial=%d\n", full_cycles, part_cycle);
                printf("\n");
                */
            } else {
                continue;
            }
        }
    }
    if(!found) {
        printf("-1\n");
    } else {
        printf("%lld\n", min_games);
    }

    return 0;
}