#include <cstdio> #include <algorithm> #include <vector> #include <map> using namespace std; typedef long long int LL; struct do_mapy { vector <LL> v; }; struct wp { vector <LL> v; vector <LL> p; map <LL, LL> m; map <LL, do_mapy> zak; vector <LL> cykl; }t[1000006]; LL c[1000006]; LL prz, nwd, cykl, dll, po, ko, sr, mni, idz, wynik; char s[1000006]; bool odw[1000006]; LL cyk[1000006], miny[1000006]; void skr (LL &j, LL a, LL b) { if (j<a) j+=b; if (b<j) j-=b; } void pk (LL a) { printf ("ok%d ", a); } int main () { LL dod, n, m, szuk; scanf ("%d", &n); for (int i=1; i<=n; i++) scanf ("%d", &c[i]); scanf ("%d%s", &m, s+1); nwd=__gcd(n, m); prz=n*m/nwd; //printf ("%d", dod); //printf ("ok"); for (LL i=1; i<=nwd; i++) { //printf ("\n%d : ", i); t[i].v.push_back(0); cykl=0; for (LL j=i; odw[j]==false; j+=(n-m), skr(j, 1, m)) { odw[j]=true; if (s[j]=='W') cykl++; else cykl--; t[i].v.push_back(j); //printf ("%d ", j); } for (vector <LL>::iterator it=t[i].v.begin()+1, kon=t[i].v.end(); it!=kon; it++) { cyk[*it]=cykl; t[i].v.push_back(*it); } } LL licznik; for (LL i=1; i<=nwd; i++) { licznik=0; t[i].p.push_back(0); for (vector<LL>::iterator it=t[i].v.begin()+1; it!=t[i].v.end(); it++) { if (s[*it]=='W') t[i].p.push_back(1); else t[i].p.push_back(-1); licznik++; t[i].p[licznik]+=t[i].p[licznik-1]; } for (LL j=1; j<=t[i].p.size()/2; j++) t[i].m[t[i].p[j]]++; //printf ("\n%d : ", i); for (LL j=0; j<=t[i].p.size()/2; j++) { //printf ("{%lld %lld}, ", t[i].p[j], t[i].v[j]); t[i].zak[t[i].p[j]].v.push_back(t[i].v[j]); } for (LL j=t[i].p.size()/2+1; j<t[i].p.size(); j++) t[i].zak[t[i].p[j]].v.push_back(t[i].v[j]+m); dll=t[i].p.size()/2; for (LL j=1; j<=dll; j++) { miny[t[i].v[j]]=t[i].p[j-1]-t[i].m.begin()->first; t[i].m[t[i].p[j+dll]]++; t[i].m[t[i].p[j]]--; if (t[i].m[t[i].p[j]]==0) t[i].m.erase(t[i].p[j]); } /*for (map<int, LL>::iterator it=t[i].m.begin(); it!=t[i].m.end(); it++) printf ("{%d %lld} ", it->first, it->second);*/ } /*for (int i=1; i<=nwd; i++) { printf ("\n%lld :\n", i); for (map<LL, do_mapy>::iterator it=t[i].zak.begin(); it!=t[i].zak.end(); it++) { printf ("%lld : ", it->first); for (vector<LL>::iterator itv=it->second.v.begin(); itv!=it->second.v.end(); itv++) printf ("%lld ", *itv); printf ("\n"); } for (LL j=0; j<t[i].p.size(); j++) printf ("{%lld %lld} ", t[i].p[j], t[i].v[j]); }*/ for (LL i=1; i<=n; i++) { cyk[i]=cyk[(i-1)%m+1]; miny[i]=miny[(i-1)%m+1]; } //printf ("\n"); licznik=1; bool minus=false; for (LL i=1; i<=n; i++) { if (cyk[i]>=0 && miny[i]<c[i]); else minus=true; } if (minus==false) { printf ("-1"); return 0; } //for (LL i=1; i<=n; i++) // printf ("%lld ", cyk[i]); //printf ("\n"); //for (LL i=1; i<=n; i++) // printf ("%lld ", miny[i]); wynik=1LL<<60; //pk(0); for (LL i=1; i<=n; i++) { po=0; ko=1LL<<60; while (po<ko) { sr=(po+ko)/2+1; //printf ("%lld %lld %lld %lld %lld %d %lld %lld\n", i, po, ko, sr, c[i]+sr*cyk[i]-miny[i], c[i], cyk[i], miny[i]); if (c[i]+sr*cyk[i]-miny[i]>=0) po=sr; else ko=sr-1; } //printf ("%lld ", po); c[i]+=po*cyk[i]; //pk(1); //printf ("{%lld %lld %lld}", (i-1)%nwd+1, licznik-1, t[(i-1)%nwd+1].p.size()); idz=0LL; int reszta=(i-1)%m+1; if (t[(i-1)%nwd+1].p.size()>=licznik) { szuk=t[(i-1)%nwd+1].p[licznik-1]-c[i]; //printf ("sz%lld %d] ", szuk, (i-1)%m+1); //pk(2); vector <LL>::iterator it=upper_bound(t[(i-1)%nwd+1].zak[szuk].v.begin(), t[(i-1)%nwd+1].zak[szuk].v.end(), reszta); //printf ("[%lld %lld] ", *it, i); //pk(3); if (it!=t[(i-1)%nwd+1].zak[szuk].v.end()) { idz=*it-reszta; idz=max(idz, c[i]-1); //printf ("{%d %d %d %lld} ", po, szuk, (i-1)%m+1, idz); idz*=n; idz+=(LL)(i); idz+=prz*po; if (idz>=0) { ///printf ("%lld ", idz); wynik=min(wynik, idz); } } } licznik++; skr(licznik, 1, m); } printf ("%lld", wynik); //printf ("\n"); //for (int k=1; k<=n; k++) printf ("%lld ", miny[k]); //for (int k=1; k<=n; k++) printf ("%lld ", cyk[k]); return 0; }
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 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 | #include <cstdio> #include <algorithm> #include <vector> #include <map> using namespace std; typedef long long int LL; struct do_mapy { vector <LL> v; }; struct wp { vector <LL> v; vector <LL> p; map <LL, LL> m; map <LL, do_mapy> zak; vector <LL> cykl; }t[1000006]; LL c[1000006]; LL prz, nwd, cykl, dll, po, ko, sr, mni, idz, wynik; char s[1000006]; bool odw[1000006]; LL cyk[1000006], miny[1000006]; void skr (LL &j, LL a, LL b) { if (j<a) j+=b; if (b<j) j-=b; } void pk (LL a) { printf ("ok%d ", a); } int main () { LL dod, n, m, szuk; scanf ("%d", &n); for (int i=1; i<=n; i++) scanf ("%d", &c[i]); scanf ("%d%s", &m, s+1); nwd=__gcd(n, m); prz=n*m/nwd; //printf ("%d", dod); //printf ("ok"); for (LL i=1; i<=nwd; i++) { //printf ("\n%d : ", i); t[i].v.push_back(0); cykl=0; for (LL j=i; odw[j]==false; j+=(n-m), skr(j, 1, m)) { odw[j]=true; if (s[j]=='W') cykl++; else cykl--; t[i].v.push_back(j); //printf ("%d ", j); } for (vector <LL>::iterator it=t[i].v.begin()+1, kon=t[i].v.end(); it!=kon; it++) { cyk[*it]=cykl; t[i].v.push_back(*it); } } LL licznik; for (LL i=1; i<=nwd; i++) { licznik=0; t[i].p.push_back(0); for (vector<LL>::iterator it=t[i].v.begin()+1; it!=t[i].v.end(); it++) { if (s[*it]=='W') t[i].p.push_back(1); else t[i].p.push_back(-1); licznik++; t[i].p[licznik]+=t[i].p[licznik-1]; } for (LL j=1; j<=t[i].p.size()/2; j++) t[i].m[t[i].p[j]]++; //printf ("\n%d : ", i); for (LL j=0; j<=t[i].p.size()/2; j++) { //printf ("{%lld %lld}, ", t[i].p[j], t[i].v[j]); t[i].zak[t[i].p[j]].v.push_back(t[i].v[j]); } for (LL j=t[i].p.size()/2+1; j<t[i].p.size(); j++) t[i].zak[t[i].p[j]].v.push_back(t[i].v[j]+m); dll=t[i].p.size()/2; for (LL j=1; j<=dll; j++) { miny[t[i].v[j]]=t[i].p[j-1]-t[i].m.begin()->first; t[i].m[t[i].p[j+dll]]++; t[i].m[t[i].p[j]]--; if (t[i].m[t[i].p[j]]==0) t[i].m.erase(t[i].p[j]); } /*for (map<int, LL>::iterator it=t[i].m.begin(); it!=t[i].m.end(); it++) printf ("{%d %lld} ", it->first, it->second);*/ } /*for (int i=1; i<=nwd; i++) { printf ("\n%lld :\n", i); for (map<LL, do_mapy>::iterator it=t[i].zak.begin(); it!=t[i].zak.end(); it++) { printf ("%lld : ", it->first); for (vector<LL>::iterator itv=it->second.v.begin(); itv!=it->second.v.end(); itv++) printf ("%lld ", *itv); printf ("\n"); } for (LL j=0; j<t[i].p.size(); j++) printf ("{%lld %lld} ", t[i].p[j], t[i].v[j]); }*/ for (LL i=1; i<=n; i++) { cyk[i]=cyk[(i-1)%m+1]; miny[i]=miny[(i-1)%m+1]; } //printf ("\n"); licznik=1; bool minus=false; for (LL i=1; i<=n; i++) { if (cyk[i]>=0 && miny[i]<c[i]); else minus=true; } if (minus==false) { printf ("-1"); return 0; } //for (LL i=1; i<=n; i++) // printf ("%lld ", cyk[i]); //printf ("\n"); //for (LL i=1; i<=n; i++) // printf ("%lld ", miny[i]); wynik=1LL<<60; //pk(0); for (LL i=1; i<=n; i++) { po=0; ko=1LL<<60; while (po<ko) { sr=(po+ko)/2+1; //printf ("%lld %lld %lld %lld %lld %d %lld %lld\n", i, po, ko, sr, c[i]+sr*cyk[i]-miny[i], c[i], cyk[i], miny[i]); if (c[i]+sr*cyk[i]-miny[i]>=0) po=sr; else ko=sr-1; } //printf ("%lld ", po); c[i]+=po*cyk[i]; //pk(1); //printf ("{%lld %lld %lld}", (i-1)%nwd+1, licznik-1, t[(i-1)%nwd+1].p.size()); idz=0LL; int reszta=(i-1)%m+1; if (t[(i-1)%nwd+1].p.size()>=licznik) { szuk=t[(i-1)%nwd+1].p[licznik-1]-c[i]; //printf ("sz%lld %d] ", szuk, (i-1)%m+1); //pk(2); vector <LL>::iterator it=upper_bound(t[(i-1)%nwd+1].zak[szuk].v.begin(), t[(i-1)%nwd+1].zak[szuk].v.end(), reszta); //printf ("[%lld %lld] ", *it, i); //pk(3); if (it!=t[(i-1)%nwd+1].zak[szuk].v.end()) { idz=*it-reszta; idz=max(idz, c[i]-1); //printf ("{%d %d %d %lld} ", po, szuk, (i-1)%m+1, idz); idz*=n; idz+=(LL)(i); idz+=prz*po; if (idz>=0) { ///printf ("%lld ", idz); wynik=min(wynik, idz); } } } licznik++; skr(licznik, 1, m); } printf ("%lld", wynik); //printf ("\n"); //for (int k=1; k<=n; k++) printf ("%lld ", miny[k]); //for (int k=1; k<=n; k++) printf ("%lld ", cyk[k]); return 0; } |