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
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int m, n;
	scanf("%d", &n);

	int koledzy[n + 1];

	for (int i = 0; i < n; i++)
		scanf("%d", &koledzy[i]);

	scanf("%d", &m);
	char bandyta[m];
	scanf("%s", bandyta);

	vector<int> sekwencje[m + 1];
	int sum[m + 1]; //ile po przejsciu sekwencji jestesmy na plusie lub minusie z pieniedzmi
	int liczba_sekwencja[m + 1]; //okresla w ktorej sekwencji jest dana liczba
	int liczba_pozycja[m + 1]; //okresla na ktorej pozycji w sekwencji jest dana liczba
	vector<int> saldo[m + 1]; //ile po zagraniu na automacie do danego momentu sekwencji jestesmy na plusie lub minusie
	vector<pair<int, int> > saldoSorted[m + 1]; //j.w. tylko posortowane

	for (int i = 0; i < m; i++)
	{
		liczba_sekwencja[i] = -1;
		sum[i] = 0;
	}

	for (int i = 0; i < m; i++)
	{
		if (liczba_sekwencja[i] == -1) //liczby nie ma jeszcze w zadnej sekwencji, tworzona jest nowa
		{
			if (bandyta[i] == 'W')
			{
				sum[i]++;
				saldo[i].push_back(1);
				saldoSorted[i].push_back(make_pair(1, 0));
			}
			else
			{
				sum[i]--;
				saldo[i].push_back(-1);
				saldoSorted[i].push_back(make_pair(-1, 0));
			}
			sekwencje[i].push_back(i);
			liczba_sekwencja[i] = i;
			liczba_pozycja[i] = 0;

			int j = (i + n) % m;
			int indx = 1; //indeks-pozycja na ktorej wstawiamy liczbe w sekwencji
			while (j != i)
			{
				if (bandyta[j] == 'W')
				{
					sum[i]++;
					saldo[i].push_back(saldo[i][indx-1] + 1);
					saldoSorted[i].push_back(make_pair(saldo[i][indx-1] + 1, -indx));
				}
				else
				{
					sum[i]--;
					saldo[i].push_back(saldo[i][indx-1] - 1);
					saldoSorted[i].push_back(make_pair(saldo[i][indx-1] - 1, -indx));
				}
				sekwencje[i].push_back(j);
				liczba_sekwencja[j] = i;
				liczba_pozycja[j] = indx;
				indx++;
				j = (j + n) % m;
			}
		}

		sort(saldoSorted[i].begin(), saldoSorted[i].end());
	}


	long long int min = (long long int)1000000000 * (long long int)1000000000;
	for (int i = 0; i < n; i++)
	{
		int ik = i % m;
		long long int result = 0;
		int poziom = 0;
		if (liczba_pozycja[ik] > 0)
			poziom = saldo[liczba_sekwencja[ik]][liczba_pozycja[ik]-1];
		
		if (sum[liczba_sekwencja[ik]] >= 0 && koledzy[i] + saldoSorted[liczba_sekwencja[ik]][0].first - poziom > 0) //suma w sekwencji nieujemna oraz nie damy razy w ramach jednej sekwencji wydac calej kasy
			continue;

		int ileSum = 0;
		if (koledzy[i] + saldoSorted[liczba_sekwencja[ik]][0].first - poziom > 0) //trzeba przechodzic cala sekwencje, liczymy ile razy
		{
			ileSum = (koledzy[i] + saldoSorted[liczba_sekwencja[ik]][0].first - poziom-1) / (-sum[liczba_sekwencja[ik]]) + 1; //TODO: do sprawdzenia czy dobrze -1 i +1 dodane
			result = (long long int)ileSum * sekwencje[liczba_sekwencja[ik]].size() * n;
		}

		int zostalo = koledzy[i] - poziom + ileSum*sum[liczba_sekwencja[ik]];
		if (zostalo > 0)
		{
			std::vector<pair<int,int> >::iterator low, up;
			low = lower_bound(saldoSorted[liczba_sekwencja[ik]].begin(), saldoSorted[liczba_sekwencja[ik]].end(), make_pair(-zostalo, -10000001));
			up = upper_bound(saldoSorted[liczba_sekwencja[ik]].begin(), saldoSorted[liczba_sekwencja[ik]].end(), make_pair(-zostalo, 10000001));

			int indx = upper_bound(low, up, make_pair(-zostalo, -liczba_pozycja[ik])) - saldoSorted[liczba_sekwencja[ik]].begin() - 1;
			if (indx < low - saldoSorted[liczba_sekwencja[ik]].begin())
				indx = up - saldoSorted[liczba_sekwencja[ik]].begin()-1;

			result = result + (long long int)((-saldoSorted[liczba_sekwencja[ik]][indx].second - liczba_pozycja[ik] + m) % m) * n + i;
		}

		if (result < min)
			min = result;
	}

	if (min == (long long int)1000000000 * (long long int)1000000000)
		printf("-1\n");
	else
		printf("%lld\n",min+1);
}