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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int MX = 2e6 + 5;
const int LOG = 10;
const LL INF = 1e18 + 5;

LL sum[LOG+2][MX], mn[LOG+2][MX], a[MX], n, m, pot2[LOG+2];
char t[MX];

LL Result = INF;

int main() 
{
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++ i)
		scanf("%lld", &a[i]);
	scanf("%lld%s", &m, t);	

	pot2[0] = 1LL;
	for (int i = 1; i <= LOG; ++ i)
		pot2[i] = (pot2[i-1] * 2LL) % m;

	for (int i = 0; i < m; ++ i)
		sum[0][i] = (t[i] == 'W' ? 1 : -1);
	for (int j = 1; j <= LOG; ++ j)
	{
		LL pos2 = (0 + (1LL << (j-1))) % m;
		for (int i = 0; i < m; ++ i)
		{
			sum[j][i] = sum[j-1][pos2];
			sum[j][i] += sum[j-1][i];
			pos2++; pos2%=m;
		}
	}

	for (int i = 0; i < m; ++ i)
		mn[0][i] = sum[0][i];
	for (int j = 1; j <= LOG; ++ j)
	{
		LL pos2 = (0 + (1LL << (j-1))) % m;
		for (int i = 0; i < m; ++ i)
		{
			mn[j][i] = min(mn[j-1][i], mn[j-1][pos2] + sum[j-1][i]);
			pos2 ++; pos2 %= m;
		}
	}

//	for (LL i = 0; i < m; ++ i){
//		printf("Pozycja %lld na cyklu\n", i);
//		for (int j = 0; j <= LOG; ++ j)
//			printf("skok o 2 ^ %lld -- suma %lld -- min %lld\n", j, sum[j][i], mn[j][i]);
//		puts("");
//	}

	int start = 0;
	for (int i = 1; i <= n; ++ i)
	{
		if (mn[LOG][start] > -a[i])
			continue;

//		printf("Sprawdzam po ilu krokach odpadnie nr %d\n", i);

		LL akt_wsp = 0LL;
		LL aktPos = start;
		LL jakDaleko = 0LL;

//		printf("zaczyna w %d\n", start);

		while (mn[0][aktPos] + akt_wsp > -a[i])
		{
//			printf("aktPos : %lld, akt_wsp : %lld\n", aktPos, akt_wsp);
//
//			printf("daleko %lld\n", jakDaleko);

			for (int j = 1; j <= LOG; ++ j)
				if (mn[j][aktPos] + akt_wsp <= -a[i])
				{	
//					printf("PRZESUWAM O 1 << %d\n", j);

					akt_wsp += sum[j-1][aktPos];
					jakDaleko += (1LL << (j-1));

					aktPos = (aktPos + (n%m) * ((1LL << (j-1))%m)) % m;
				
					break;
				}
		}	

//		printf("aktPos: %lld, akt_wsp: %lld, jakDaleko %lld\n", aktPos, akt_wsp, jakDaleko);

		Result = min(Result, (jakDaleko)*n + i);

		start ++; start %= m;				
	}

	if (Result >= INF)
		puts("-1");
	else
		printf("%lld\n", Result);

	return 0;
}