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
#include<bits/stdc++.h>
const int mln=2000001;
long long tab[mln];
char s[mln+5];
int odw[mln];
long long pref[2*mln], war[2*mln], num[2*mln], stos[2*mln], gdzie[2*mln];
using namespace std;
long long ma=-1;
int main()
{
    long long n,m;
    scanf("%lld", &n);
    for(int i=0; i<n; i++)
        scanf("%lld", &tab[i]);
    scanf("%lld", &m);
    scanf("%s", s);
    if(m<n){
        int k=(m+n-1)/m;
        for(int i=1; i<k; i++)
            for(int j=0; j<m; j++)
                s[j+i*m]=s[j];
        m*=k;
    }
    //printf("%s",s);
    for(int dz=0; dz<n; dz++)
        if(odw[dz]==0)
        {
            long long x=dz;
            long long ile=0;
            while(odw[x]==0)
            {
                odw[x]=1;
                    //printf("%lld\n", x);
                    ile++;
                    num[ile]=x;
                    if(s[x]=='W')
                        war[ile]=1;
                    if(s[x]=='P')
                        war[ile]=-1;

                x=(x+n)%m;
            }
            long long sum=0;
            for(int i=1; i<=ile; i++)
            {
                sum+=war[i];
                war[ile+i]=war[i];
                num[ile+i]=num[i];
                pref[i]=pref[i-1]+war[i];
            }
            for(int i=ile+1; i<=2*ile; i++)
                pref[i]=pref[i-1]+war[i];
            int g=0;
            stos[0]=1000000009;
            for(int i=2*ile; i>0; i--)
            {
                g++;
                while(g>0 && pref[i]<stos[g-1])
                    g--;
                stos[g]=pref[i];
                gdzie[g]=i;
                if(num[i]<n && i<=ile)
                {
                    long long wyn=0;
                    long long x=tab[num[i]], t=pref[i-1];
                    //printf("! %lld %lld\n", x, t);
                    if(stos[0]-t >= 0)
                        continue;
                    //printf("? %lld %lld\n", stos[0], t);
                    if(stos[0]-t +x > 0)
                    {
                        if(sum>=0)
                            continue;
                        long long x2=(x+stos[0]-t-sum-1)/(-sum);
                        wyn+=x2*ile*n;
                        //printf("++ %lld\n", x2);
                        x+=sum*x2;
                    }
                    int pocz=0, kon=g;
                    while(pocz < kon)
                    {
                        int s=(pocz+kon+1)/2;
                        if(x+stos[s]-t<=0)
                            pocz=s;
                        else
                            kon=s-1;
                    }
                    wyn+=(gdzie[pocz]-i)*n;
                    wyn+=num[i]+1;
                    if(ma==-1 || ma>wyn)
                        ma=wyn;
                    //printf("%lld %lld\n", num[i], wyn);
                }
            }
        }
    printf("%lld\n", ma);
}