oj.uz

Submission #117674

# Submission time Handle Problem Language Result Execution time Memory
117674 2019-06-17T05:50:34 Z 송준혁(#2882) Ljetopica (COI19_ljetopica) C++14
22 / 100
 65 ms 22180 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;

int N, K;
int P[1010], now[1010];
int A[1010], B[1010];
LL C[1010][1010];
LL D1[1010][1010];
LL D2[1010][1010];
bool chk1[1010][1010];
bool chk2[1010][1010];
LL twoPow[1010], ans;

LL comb(int n, int r){
    if (n < r || r < 0) return 0;
    if (n == r || r == 0) return 1;
    if (C[n][r]) return C[n][r];
    return C[n][r] = (comb(n-1, r-1) + comb(n-1, r)) % MOD;
}

pii f1(int lv, int k, bool l, bool r){
    if (l && now[lv] < A[lv]) return pii(0, 0);
    if (now[lv] > A[lv]) l = false;
    if (r && now[lv] > B[lv]) return pii(0, 0);
    if (now[lv] < B[lv]) r = false;
    if (lv >= N){
        if (k == K) return pii(0, 1);
        return pii(0, 0);
    }

    if (!l && !r && chk1[lv][k]) return pii(D1[lv][k], comb(N-lv, K-k));
    LL t = 0;
    pii ret1, ret2;
    now[lv+1] = P[lv+1] ^ ((K-k) & 1);
    ret1 = f1(lv+1, k, l, r);
    now[lv+1] = P[lv+1] ^ ((K-k-1) & 1);
    ret2 = f1(lv+1, k+1, l, r);
    if (P[lv+1] ^ ((K-k) & 1)) t = (t + ret1.second * twoPow[N-lv-1]) % MOD;
    else t = (t + ret2.second * twoPow[N-lv-1]) % MOD;
    t = (t + ret1.first + ret2.first) % MOD;
    if (!l && !r){
        chk1[lv][k] = true;
        D1[lv][k] = t;
    }
    return pii(t, ret1.second + ret2.second);
}

pii f2(int lv, int k, bool l, bool r){
    if (l && now[lv] < A[lv]) return pii(0, 0);
    if (now[lv] > A[lv]) l = false;
    if (r && now[lv] > B[lv]) return pii(0, 0);
    if (now[lv] < B[lv]) r = false;
    if (lv >= N){
        if (k == K) return pii(0, 1);
        return pii(0, 0);
    }

    if (!l && !r && chk2[lv][k]) return pii(D2[lv][k], comb(N-lv, K-k));
    LL t = 0;
    pii ret1, ret2;
    now[lv+1] = P[lv+1] ^ ((K-k-1) & 1);
    ret1 = f2(lv+1, k, l, r);
    now[lv+1] = P[lv+1] ^ ((K-k) & 1);
    ret2 = f2(lv+1, k+1, l, r);
    if (P[lv+1] ^ ((K-k-1) & 1)) t = (t + ret1.second * twoPow[N-lv-1]) % MOD;
    else t = (t + ret2.second * twoPow[N-lv-1]) % MOD;
    t = (t + ret1.first + ret2.first) % MOD;
    if (!l && !r){
        chk2[lv][k] = true;
        D2[lv][k] = t;
    }
    return pii(t, ret1.second + ret2.second);
}

int main(){
    char ch;
    scanf("%d %d", &N, &K);
    for (int i=2; i<=N; i++){
        scanf(" %c", &ch);
        if (ch == 'R') P[i] = 1;
    }
    for (int i=1; i<=N; i++) scanf("%1d", &A[i]);
    for (int i=1; i<=N; i++) scanf("%1d", &B[i]);
    twoPow[0] = 1;
    for (int i=1; i<=N; i++) twoPow[i] = (twoPow[i-1] * 2) % MOD;
    now[1] = 1;
    pii ret1 = f1(1, 0, true, true);
    pii ret2 = f2(1, 0, true, true);
    printf("%lld\n", (ret1.first + ret1.second*twoPow[N-1] + ret2.first + ret2.second*twoPow[N-1]) % MOD);
    return 0;
}

Compilation message

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~~
ljetopica.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &ch);
         ~~~~~^~~~~~~~~~~~
ljetopica.cpp:85:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%1d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~~
ljetopica.cpp:86:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%1d", &B[i]);
                              ~~~~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 23 ms 10880 KB Output is correct
8 Correct 3 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 23 ms 10880 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 640 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 2 ms 640 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Incorrect 65 ms 22180 KB Output isn't correct
25 Halted 0 ms 0 KB -