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
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <time.h>
#include <queue>

using namespace std;

typedef long long int int64;

typedef struct {
	vector<int64> indices;
	vector<int64> values;
	vector<int64> pref_min, suf_min;
	map<int64, vector<int64> > values_map;
	int64 min_value;
} Cycle;

int main () {
	int64 n, m, a;
	scanf("%lld", &n);
	vector<int64> start;
	start.reserve(n + 4);
	for (int64 i = 0; i < n; ++i) {
		scanf("%lld", &a);
		start.push_back(a);
	}
	scanf("%lld", &m);
	char c;
	vector<int64> machine_cycle;
	machine_cycle.reserve(m + 4);
	scanf("%c", &c);
	for (int64 i = 0; i < m; ++i) {
		scanf("%c", &c);
		machine_cycle.push_back(c == 'W' ? 1 : -1);
	}

	vector<int64> cycle_number(m, -1);
	vector<int64> order_in_cycle(m, -1);
	Cycle empty;
	empty.min_value = 1;
	vector<Cycle> cycles;
	for (int64 i = 0; i < m; ++i) {
		if (cycle_number[i] != -1) {
			continue;
		}
		int64 k = 0;
		int64 value = 0;
		int64 cnum = cycles.size();
		cycle_number[i] = cnum;
		order_in_cycle[i] = 0;
		cycles.push_back(empty);
		cycles[cnum].indices.push_back(i);
		value += machine_cycle[i];
		cycles[cnum].values.push_back(value);
		cycles[cnum].values_map[value].push_back(k);
		cycles[cnum].min_value = min(cycles[cnum].min_value, value);
		int64 j = (i + n) % m;
		while (j != i) {
			++k;
			order_in_cycle[j] = k;
			cycle_number[j] = i;
			cycles[cnum].indices.push_back(j);
			value += machine_cycle[j];
			cycles[cnum].values.push_back(value);
			cycles[cnum].values_map[value].push_back(k);
			cycles[cnum].min_value = min(cycles[cnum].min_value, value);
			j = (j + n) % m;
		}
	}

	for (int64 i = 0; i < cycles.size(); ++i) {
		int64 pref_min = cycles[i].values[0];
		for (int64 j = 0; j < cycles[i].values.size(); ++j) {
			pref_min = min(pref_min, cycles[i].values[j]);
			cycles[i].pref_min.push_back(pref_min);
		}
		int64 suf_min = cycles[i].values[cycles[i].values.size() - 1];
		for (int64 j = 0; j < cycles[i].values.size(); ++j) {
			suf_min = min(suf_min, cycles[i].values[cycles[i].values.size() - 1 - j]);
			cycles[i].suf_min.push_back(suf_min);
		}
	}

	int64 min_bank = -1LL;

	for (int64 i = 0; i < n; ++i) {
		int64 cycle = cycle_number[i % m];
		int64 offset = order_in_cycle[i % m];
		int64 s = start[i];
		int64 suf_min = cycles[cycle].suf_min[cycles[cycle].values.size() - offset - 1];
		int64 value = (offset ? cycles[cycle].values[offset - 1] : 0);
		int64 pref_min = cycles[cycle].pref_min[offset - 1];
		int64 last = cycles[cycle].values[cycles[cycle].values.size() - 1];
		int64 min_drop = min(suf_min - value, pref_min - value + last);

		int64 extra_cycles = 0LL;
		if ((last >= 0) && (-min_drop < s)) {
			continue;
		}
		else if (last < 0) {
			int64 num = s + min_drop;
			int64 den = -last;
			if (num > 0) {
				int64 q = num % den;
				int64 val = q ? num / den + 1 : num / den;
				extra_cycles = max(0LL, val);
			}
		}

		int64 rounds = extra_cycles * cycles[cycle].values.size();
		s += last * extra_cycles;

		int64 extra_rounds = 0;
		vector<int64>::iterator it = lower_bound(cycles[cycle].values_map[value - s].begin(), cycles[cycle].values_map[value - s].end(), offset);
		if (it == cycles[cycle].values_map[value - s].end()) {
			int64 bound = cycles[cycle].values_map[value - s - last][0];
			extra_rounds = cycles[cycle].values.size() - offset + bound + 1;
		}
		else {
			extra_rounds = *it - offset + 1;
		}
		int64 plays = (rounds + extra_rounds - 1) * n + i + 1;
		if (min_bank == -1LL) {
			min_bank = plays;
		}
		min_bank = min(min_bank, plays);
	}
	printf("%lld\n", min_bank);

	return 0;
}