oj.uz

Submission #72379

# Submission time Handle Problem Language Result Execution time Memory
72379 2018-08-26T07:34:14 Z BOJ 8481(#2179, veydpz, jh05013, 16silver) Dstorv (FXCUP3_dstorv) C++17
9 / 100
 3 ms 704 KB 
#include <cstdio>
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(){
    scanf("%lld%lld%lld",&N,&r,&h);
    scanf("%s",s);
    scanf("%lld%lld",&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) printf("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;
            printf("%lld",ans);
        }
    }
}

Compilation message

dstorv.cpp: In function 'int main()':
dstorv.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&N,&r,&h);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dstorv.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",s);
     ~~~~~^~~~~~~~
dstorv.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&A,&B);
     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 3 ms 536 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 660 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 3 ms 704 KB Output is correct
12 Correct 3 ms 704 KB Output is correct
13 Correct 3 ms 704 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 704 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 256 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 3 ms 536 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 660 KB Output is correct
10 Correct 2 ms 704 KB Output is correct
11 Correct 3 ms 704 KB Output is correct
12 Correct 3 ms 704 KB Output is correct
13 Correct 3 ms 704 KB Output is correct
14 Incorrect 2 ms 704 KB Output isn't correct
15 Halted 0 ms 0 KB -