oj.uz

Submission #611648

# Submission time Handle Problem Language Result Execution time Memory
611648 2022-07-29T06:17:05 Z 반딧불(#8497) Ljetopica (COI19_ljetopica) C++17
8 / 100
 500 ms 18596 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 1000000007;

int n, k;
bool dir[1002];
ll comb[1002][1002]; /// comb[i][j] : iCj
ll pow2[1002];
ll DP[1002][1002][2]; /// DP[i][j][b]: ���� ���� i�� ��忡 �ְ�, �¿츦 j�� �ٲ� �� �ְ�, (k=1�̸� ���� �¿츦 �ݴ�� ���� ��) ���� ��
bool A[1002], B[1002];
ll ans;

inline void addAns(ll x){
    ans = (ans + x) % MOD;
}

void dfs(int depth, int chance, bool following, ll offset, bool isBiggerThanA, bool isSmallerThanB){
    if(chance < 0) return;
    if(depth==n){
        if(!chance) addAns(offset+1);
        return;
    }
    if(isBiggerThanA && isSmallerThanB){ /// �ܼ� ����� ������ ���̽�
        addAns(DP[depth][chance][following] + comb[n-depth][chance] * offset);
    }

    if(!(!isBiggerThanA && A[depth] == 1)){ /// �������� ���� ���� ���̴�
        bool toFollow = !dir[depth];
        dfs(depth+1, chance - (following ^ toFollow), toFollow, (offset+pow2[n-depth-1])%MOD, isBiggerThanA, (B[depth] == 1) || isSmallerThanB);
    }
    if(!(!isSmallerThanB && B[depth] == 0)){ /// ���������� ���� ���� ���̴�
        bool toFollow = dir[depth];
        dfs(depth+1, chance - (following ^ toFollow), toFollow, (offset+pow2[n-depth])%MOD, (A[depth] == 0 || isBiggerThanA), isSmallerThanB);
    }
}

int main(){
    for(int i=0; i<=1000; i++){
        comb[i][0] = comb[i][i] = 1;
        for(int j=1; j<i; j++) comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
    }
    pow2[0] = 1;
    for(int i=1; i<=1000; i++) pow2[i] = pow2[i-1] * 2 % MOD;

    scanf("%d %d", &n, &k);
    for(int i=1; i<n; i++){
        char c;
        scanf(" %c", &c);
        dir[i] = (c == 'R');
    }

    DP[n][0][0] = DP[n][0][1] = 1;
    for(int d=n-1; d>=1; d--){ /// ���� ����
        for(int j=0; j<=n-d; j++){
            ll cntNo = comb[n-d-1][j], cntYes = j ? comb[n-d-1][j-1] : 0;
            DP[d][j][0] += (DP[d+1][j][0] + (!dir[d] ? pow2[n-d-1] : pow2[n-d]) * cntNo);
            if(j) DP[d][j][0] += (DP[d+1][j-1][1] + (dir[d] ? pow2[n-d-1] : pow2[n-d]) * cntYes);
            DP[d][j][0] %= MOD;

            if(j) DP[d][j][1] += (DP[d+1][j-1][0] + (!dir[d] ? pow2[n-d-1] : pow2[n-d]) * cntYes);
            DP[d][j][1] += (DP[d+1][j][1] + (dir[d] ? pow2[n-d-1] : pow2[n-d]) * cntNo);
            DP[d][j][1] %= MOD;

//            printf("(%d %d): (%lld %lld)\n", d, j, DP[d][j][0], DP[d][j][1]);
        }
    }

    for(int i=0; i<n; i++) scanf("%1d", &A[i]);
    for(int i=0; i<n; i++) scanf("%1d", &B[i]);
    for(int i=0; i<n; i++){
        if(A[i] < B[i]) break;
        if(A[i] > B[i]){
            puts("0");
            return 0;
        }
    }

    dfs(1, k, 0, 0, 0, 0);
    dfs(1, k, 1, 0, 0, 0);
    printf("%lld", ans);
}

Compilation message

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:71:37: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'bool*' [-Wformat=]
   71 |     for(int i=0; i<n; i++) scanf("%1d", &A[i]);
      |                                   ~~^   ~~~~~
      |                                     |   |
      |                                     |   bool*
      |                                     int*
ljetopica.cpp:72:37: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'bool*' [-Wformat=]
   72 |     for(int i=0; i<n; i++) scanf("%1d", &B[i]);
      |                                   ~~^   ~~~~~
      |                                     |   |
      |                                     |   bool*
      |                                     int*
ljetopica.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ljetopica.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~
ljetopica.cpp:71:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     for(int i=0; i<n; i++) scanf("%1d", &A[i]);
      |                            ~~~~~^~~~~~~~~~~~~~
ljetopica.cpp:72:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     for(int i=0; i<n; i++) scanf("%1d", &B[i]);
      |                            ~~~~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 18516 KB Output is correct
2 Correct 16 ms 17748 KB Output is correct
3 Correct 14 ms 17008 KB Output is correct
4 Correct 15 ms 16096 KB Output is correct
5 Correct 10 ms 15348 KB Output is correct
6 Correct 10 ms 14556 KB Output is correct
7 Correct 9 ms 13880 KB Output is correct
8 Correct 9 ms 13112 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 18596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 18516 KB Output is correct
2 Correct 16 ms 17748 KB Output is correct
3 Correct 14 ms 17008 KB Output is correct
4 Correct 15 ms 16096 KB Output is correct
5 Correct 10 ms 15348 KB Output is correct
6 Correct 10 ms 14556 KB Output is correct
7 Correct 9 ms 13880 KB Output is correct
8 Correct 9 ms 13112 KB Output is correct
9 Incorrect 19 ms 7252 KB Output isn't correct
10 Halted 0 ms 0 KB -