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
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;
int N,M;
vector<int>hajs,gra;
vector<int>bylo,poz;
string Sgra;
void wczytaj(){
    cin>>N; hajs.resize(N);
    for(int i=0;i<N;i++){
	cin>>hajs[i];
    }
    
    cin>>M>>Sgra;
    bylo.resize(M);
    gra.resize(M); poz.resize(2*M+666);
    for(int i=0;i<M;i++)
	if(Sgra[i]=='P')
	    gra[i]=1;
	else
	    gra[i]=-1;
}

int booster,cykl;
vector<int>tree;
int maxx(int l,int r){
    l+=booster; r+=booster;
    int odp=max(tree[l],tree[r]);
    while(l/2 != r/2){
	if(l%2==0)
	    odp=max(odp,tree[l+1]);
	if(r%2==1)
	    odp=max(odp,tree[r-1]);
	l/=2;
	r/=2;
    }
    return odp;
}
int znajdz(int p,int x){
    p+=booster;
    int y;
    if(tree[p]>=x)return p-booster;
    while(p>1){
	if(tree[p+1]>=x){
	    y=p+1;
	    break;
	}
	p/=2;
    }
    while(y<booster){
	if(tree[2*y]>=x)
	    y=y*2;
	else
	    y=2*y+1;
    }
    return y-booster;
}
long long ANS=-1;
void solve(int kto,int gd){//ktory kolega, gdzie w drzewie
    long long int odj=tree[gd+booster-1];//to co odejmujemy zeby sumy pref byly spoko
    long long int najw=maxx(gd,gd+cykl)-odj;//ile najwiecej strace
    long long int kasa=hajs[kto];//ile moge wydac
    long long int dcykl=tree[gd+cykl+booster]-odj;//ile co cykl trace/zyskuje
    long long int kon;//gdzie przegrywa
    if(najw<kasa && dcykl<=0){//on nigdy nie przegra!!!
	return;
    }
    //printf("kto=%d gd=%d odj=%d najw=%d kasa=%d dcykl=%d cykl=%d\n",
	//   kto,gd,odj,najw,kasa,dcykl,cykl);
    if(najw>=kasa){
	kon=znajdz(gd,kasa+odj);//tu moze byc blad!!!!!!!!!!!! ale raczej spoko
	//printf("easy kon=%d\n",kon);
	if((ANS==-1 || (1LL*(kon-gd)*N+kto+1)<ANS) && (1LL*(kon-gd)*N+kto+1)>0){
	    ANS=1LL*(kon-gd)*N+kto+1;
	  //  printf("%lld safsfas\n",ANS);
	}
    }
    long long int ileOb=(kasa-najw)/dcykl;//ile obiegow cykli
    long long int ileTr=(dcykl*ileOb);//ile trace po cyklach
    
    kon=znajdz(gd,kasa+odj-ileTr);//tu moze byc blad!!!!!!!!!!!! ale raczej spoko
    //printf("kon=%d\n",kon);
    //if(kon-gd<0)cout<<"dupa";
    if((ANS==-1 || (1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N)<ANS)  && (1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N)>0)
	ANS=1LL*(cykl+1)*N*ileOb+kto+1LL+1LL*(kon-gd)*N;
}
vector<pair<int,int> >stos;//kto gdzie
void dodaj(int x,int pz){
    while(x<N){
	stos.push_back(make_pair(x,pz));
	x+=M;
    }
}
void sciagaj(){
    while(!stos.empty()){
	solve(stos.back().first,stos.back().second);
	stos.pop_back();
    }
}
void makeTree(int kon){
    cykl=((kon-1)/2)-1;//dl cyklu
    booster=2;
    while(kon>booster)
	booster*=2;
    
    tree.resize(0);
    tree.resize(2*booster+2);
    for(int i=booster+1;i<booster+kon;i++){
	tree[i]=gra[poz[i-booster]];
	tree[i]+=tree[i-1];
    }
    for(int i=booster-1;i>=1;i--)
	tree[i]=max(tree[2*i],tree[2*i+1]);
    //for(int i=booster+1;i<booster+kon;i++)
	//printf("%d: %d\n",i-booster,tree[i]);
}
void skacz(){
    for(int i=0;i<M;i++){
	int p=i,j=1;//p pozycja dla stanu W,P, j pozycja w drzewie
	while(bylo[p]<2){
	    //printf("p=%d j=%d\n",p,j);
	    if(bylo[p]==0)dodaj(p,j);
	    poz[j]=p;//jaki stan na j tej pozycji w drzewie
	    bylo[p]++;
	    j++;
	    p=(p+N)%M;
	}
	//printf("  %d  \n",j);
	if(j>1)makeTree(j);//j ilosc elementow
	sciagaj();
    }
}
int main(){
    cout.sync_with_stdio(0);
    
    wczytaj();
    
    skacz();
    
    cout<<ANS;
    return 0;
}