oj.uz

Submission #14223

# Submission time Handle Problem Language Result Execution time Memory
14223 2015-05-05T10:39:58 Z gs14004 선다형 시험 (TOKI14_multiple) C++14
40 / 100
 70 ms 50456 KB 
#include <cstdio>
#include <cstring>
const int mod = 1e9 + 7;

int n, p, q;
char sa[2005], sb[2005];
char tab[2005][6];

int dp[205][205][205];
int bino[2005][2005];

int f(int pos, int p, int q){
    if(p < 0 || q < 0) return 0;
    if(pos == n) return p == 0 && q == 0;
    if(~dp[pos][p][q]) return dp[pos][p][q];
    int ret = 0;
    for (int i=0; i<5; i++) {
        if(tab[pos][i] != '.'){
            ret += f(pos+1,p - (sa[pos] == tab[pos][i]),q - (sb[pos] == tab[pos][i]));
            ret %= mod;
        }
    }
    return dp[pos][p][q] = ret;
}

void solve_sub2(){
    int cnt_nomatch = 0;
    int cnt_amatch = 0;
    int cnt_bmatch = 0;
    int cnt_abmatch = 0;
    int cnt_samematch = 0;
    for (int i=0; i<n; i++) {
        if(tab[i][sa[i] - 'a'] != '.' && sa[i] == sb[i]){
            cnt_samematch++;
        }
        else if(tab[i][sa[i] - 'a'] != '.' && tab[i][sb[i] - 'a'] != '.'){
            cnt_abmatch++;
        }
        else if(tab[i][sa[i] - 'a'] != '.'){
            cnt_amatch++;
        }
        else if(tab[i][sb[i] - 'a'] != '.'){
            cnt_bmatch++;
        }
        else{
            cnt_nomatch++;
        }
    }
    for (int i=0; i<=n; i++) {
        bino[i][0] = 1;
        for (int j=1; j<=i; j++) {
            bino[i][j] = bino[i-1][j] + bino[i-1][j-1];
            bino[i][j] %= mod;
        }
    }
    int ret = 0;
    for (int i=0; i<=cnt_samematch; i++) {
        for (int j=0; j<=cnt_abmatch; j++) {
            int pmatch = p - i - j;
            int qmatch = q - i - (cnt_abmatch - j);
            if(pmatch < 0 || qmatch < 0) continue;
            long long t = 1ll * bino[cnt_amatch][pmatch] * bino[cnt_bmatch][qmatch] % mod;
            t *= bino[cnt_samematch][i];
            t %= mod;
            t *= bino[cnt_abmatch][j];
            t %= mod;
            ret += t;
        }
    }
    for (int j=0; j<cnt_nomatch; j++) {
        ret <<= 1;
        ret %= mod;
    }
    printf("%d",ret);
}

void what_the_fuck(){
    char str[10];
    memset(dp,-1,sizeof(dp));
    scanf("%d %d %d",&n,&p,&q);
    for (int i=0; i<n; i++) {
        scanf("%s",str);
        sa[i] = str[0];
    }
    for (int i=0; i<n; i++) {
        scanf("%s",str);
        sb[i] = str[0];
    }
    for (int i=0; i<n; i++) {
        scanf("%s",tab[i]);
    }
    if(n > 200){
        solve_sub2();
        return;
    }
    printf("%d",f(0,p,q));
}

int main(){
    what_the_fuck();
    puts("");
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 50456 KB Output is correct
2 Correct 0 ms 50456 KB Output is correct
3 Correct 4 ms 50456 KB Output is correct
4 Correct 4 ms 50456 KB Output is correct
5 Correct 3 ms 50456 KB Output is correct
6 Correct 3 ms 50456 KB Output is correct
7 Correct 7 ms 50456 KB Output is correct
8 Correct 0 ms 50456 KB Output is correct
9 Correct 30 ms 50456 KB Output is correct
10 Correct 70 ms 50456 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 50456 KB Output is correct
2 Correct 7 ms 50456 KB Output is correct
3 Correct 4 ms 50456 KB Output is correct
4 Correct 12 ms 50456 KB Output is correct

Subtask #3
0.0 / 60.0

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