#include <cstdio> #include <vector> #include <algorithm> using namespace std; char _A[1000006]; char A[1000006]; int _M[1000006]; int M[1000006]; int _S[2000006]; int PP[1000006]; class { public: int A[ 5000006 ]; int size; void setup( int *tab, int n ) { size=2; while ( size<n ) size*=2; for ( int i=0; i<n; i++ ) A[size+i]=tab[i]; for ( int i=size+n; i<=2*size; i++ ) A[i]=-3000006; for ( int i=size-1; i>0; i-- ) A[i]=max(A[2*i],A[2*i+1]); A[0]=-3000006; } int mx( int b, int e ) { b+=size; e+=size; int r = max( A[b], A[e] ); while (b/2<e/2) { if (!(b&1)) r=max(r,A[b+1]); if ( e&1 ) r=max(r,A[e-1]); b>>=1; e>>=1; } return r; } int find_next( int b, int v ) { b += size; if ( A[b] >= v ) return b-size; while ( 1 ) { if ( !(b&1) && A[b+1]>=v ) { b++; break; } b>>=1; } while ( b<size ) { b<<=1; if ( A[b]<v ) b++; } return b-size; } } T; long long process( int n, int m ) { long long w = 3e18; int p = 0; int s = 0; _S[0]=0; int *S=_S+1; for ( int i=0; i<2*m; i++ ) { if ( A[p] == 'W' ) s--; else s++; S[i]=s; if ( i<m ) PP[p]=i; p=(p+n)%m; } T.setup( S, 2*m ); for ( int _i=0; _i<n; _i++ ) { int mm = M[_i]; int i=PP[_i%m]; int mx = T.mx(i,i+m-1)-S[i-1]; int s = S[i+m-1]-S[i-1]; if ( mx <= 0 ) continue; int a = 0; if ( s > 0 ) { a = max( 0, (mm-mx+s-1)/s ); mm -= a*s; } if ( mm > mx ) continue; long long _w = ((long long)a)*m; if ( mm ) { int aa = T.find_next( i, mm+S[i-1] )-i; _w += aa; } w=min( w, _w*n+_i ); } return w; } int nwd( int a, int b ) { if (a&&b) return nwd(b,a%b); return a+b; } int main() { /*int AA[] = { 1,2,3,12,5 }; T.setup( AA, 5 ); printf("%d\n",T.find_next(1,4)); return 0;// */ int n,m; scanf("%d",&n); for ( int i=0; i<n; i++ ) scanf("%d",_M+i); scanf("%d",&m); scanf("%s",_A); int dz = nwd( n, m ); //if (dz!=1) printf("%d ",dz); //return 0; long long w = 3e18; for ( int i=0; i<dz; i++ ) { for ( int j=i; j<n; j+=dz ) M[j/dz]=_M[j]; for ( int j=i; j<m; j+=dz ) A[j/dz]=_A[j]; long long _w = process( n/dz, m/dz ); if ( _w != 3e18 ) w = min( w, _w*dz+i+1 ); } if ( w == 3e18 ) printf("-1\n"); else printf("%lld\n",w); 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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; char _A[1000006]; char A[1000006]; int _M[1000006]; int M[1000006]; int _S[2000006]; int PP[1000006]; class { public: int A[ 5000006 ]; int size; void setup( int *tab, int n ) { size=2; while ( size<n ) size*=2; for ( int i=0; i<n; i++ ) A[size+i]=tab[i]; for ( int i=size+n; i<=2*size; i++ ) A[i]=-3000006; for ( int i=size-1; i>0; i-- ) A[i]=max(A[2*i],A[2*i+1]); A[0]=-3000006; } int mx( int b, int e ) { b+=size; e+=size; int r = max( A[b], A[e] ); while (b/2<e/2) { if (!(b&1)) r=max(r,A[b+1]); if ( e&1 ) r=max(r,A[e-1]); b>>=1; e>>=1; } return r; } int find_next( int b, int v ) { b += size; if ( A[b] >= v ) return b-size; while ( 1 ) { if ( !(b&1) && A[b+1]>=v ) { b++; break; } b>>=1; } while ( b<size ) { b<<=1; if ( A[b]<v ) b++; } return b-size; } } T; long long process( int n, int m ) { long long w = 3e18; int p = 0; int s = 0; _S[0]=0; int *S=_S+1; for ( int i=0; i<2*m; i++ ) { if ( A[p] == 'W' ) s--; else s++; S[i]=s; if ( i<m ) PP[p]=i; p=(p+n)%m; } T.setup( S, 2*m ); for ( int _i=0; _i<n; _i++ ) { int mm = M[_i]; int i=PP[_i%m]; int mx = T.mx(i,i+m-1)-S[i-1]; int s = S[i+m-1]-S[i-1]; if ( mx <= 0 ) continue; int a = 0; if ( s > 0 ) { a = max( 0, (mm-mx+s-1)/s ); mm -= a*s; } if ( mm > mx ) continue; long long _w = ((long long)a)*m; if ( mm ) { int aa = T.find_next( i, mm+S[i-1] )-i; _w += aa; } w=min( w, _w*n+_i ); } return w; } int nwd( int a, int b ) { if (a&&b) return nwd(b,a%b); return a+b; } int main() { /*int AA[] = { 1,2,3,12,5 }; T.setup( AA, 5 ); printf("%d\n",T.find_next(1,4)); return 0;// */ int n,m; scanf("%d",&n); for ( int i=0; i<n; i++ ) scanf("%d",_M+i); scanf("%d",&m); scanf("%s",_A); int dz = nwd( n, m ); //if (dz!=1) printf("%d ",dz); //return 0; long long w = 3e18; for ( int i=0; i<dz; i++ ) { for ( int j=i; j<n; j+=dz ) M[j/dz]=_M[j]; for ( int j=i; j<m; j+=dz ) A[j/dz]=_A[j]; long long _w = process( n/dz, m/dz ); if ( _w != 3e18 ) w = min( w, _w*dz+i+1 ); } if ( w == 3e18 ) printf("-1\n"); else printf("%lld\n",w); return 0; } |