oj.uz

Submission #72423

# Submission time Handle Problem Language Result Execution time Memory
72423 2018-08-26T08:02:07 Z BOJ 8481(#2179, veydpz, jh05013, 16silver) Dstorv (FXCUP3_dstorv) C++17
9 / 100
 4 ms 668 KB 
#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

char s[7777];
char st[7777];
int top, idx;
const long long P=1000000007LL;
long long N,r,h,A,B,nofr,nofh;
long long ans,ansans;
long long llpow(long long x, long long n){
    if(n==1) return x;
    long long h=llpow(x,n/2);
    if(n&1) return ((h*h)%P*x)%P;
    return (h*h)%P;
}
long long invrh;
void push(char c){
    st[++top]=c;
}

int main(){OJize();
    cin>>N>>r>>h>>s>>A>>B;
    invrh=llpow(r+h,P-2);
    ans=1LL;
    nofr=nofh=0;
    for(int i=0;i<N;i++){
        if(s[i]=='R') nofr++;
        else nofh++;
    }
    for(int i=0;i<nofr-A;i++){
        ans=((ans*r)%P*invrh)%P;
    }
    for(int i=0;i<nofh-B;i++){
        ans=((ans*h)%P*invrh)%P;
    }
    if(N<=15){
        if(nofr<A || nofh<B) cout<<0;
        else{
            ansans=0LL;
            for(int i=0;i<(1<<(N-A-B));i++){
                top=-1;
                idx=0;
                for(int j=0;j<N-A-B;j++){
                    while(idx <= N){
                        if(top > 0 && st[top]=='H' && st[top-1]=='R') break;
                        if(idx!=N) push(s[idx]);
                        idx++;
                    }
                    if(idx>N) break;
                    if(i&(1<<j)){
                        top--;
                    }
                    else{
                        top--;
                        st[top]='H';
                    }
                }
                for(;idx<N;idx++) push(s[idx]);
                if(top==A+B-1){
                    int k;
                    for(k=0;k<B;k++){
                        if(st[k]!='H') break;
                    }
                    if(k==B){
                        for(k=0;k<A;k++){
                            if(st[B+k]!='R') break;
                        }
                        if(k==A) ansans++;
                    }
                }
            }
            ans=(ans*ansans)%P;
            cout<<ans;
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 668 KB Output is correct
7 Correct 4 ms 668 KB Output is correct
8 Correct 3 ms 668 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 668 KB Output is correct
12 Correct 2 ms 668 KB Output is correct
13 Correct 3 ms 668 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 668 KB Output is correct
7 Correct 4 ms 668 KB Output is correct
8 Correct 3 ms 668 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 668 KB Output is correct
12 Correct 2 ms 668 KB Output is correct
13 Correct 3 ms 668 KB Output is correct
14 Incorrect 3 ms 668 KB Output isn't correct
15 Halted 0 ms 0 KB -