oj.uz

Submission #611645

# Submission time Handle Problem Language Result Execution time Memory
611645 2022-07-29T06:15:36 Z 이동현(#8500) Ljetopica (COI19_ljetopica) C++17
0 / 100
 22 ms 16104 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod = (int)1e9 + 7;

int n, k;
string s;
int dp[1004][1004][2][2];

int sol(string f, int mst){
    f = f.substr(1);
    memset(dp, 0, sizeof(dp));
    dp[0][0][0][0] = dp[0][0][1][0] = 1;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j <= k; ++j){
            for(int x = 0; x < 2; ++x){
                for(int y = 0; y < 2; ++y){
                    if(!dp[i][j][x][y]) continue;
                    int num = ((s[i] == 'R') ^ x);
                    if(!num){
                        dp[i + 1][j][x][y | (num < f[i] - '0')] = (dp[i + 1][j][x][y | (num < f[i] - '0')] + (dp[i][j][x][y] << 1)) % mod;
                        if((y || f[i] - '0' == 1) && j + 1 <= k){
                            dp[i + 1][j + 1][x ^ 1][y] = (dp[i + 1][j + 1][x ^ 1][y] + ((dp[i][j][x][y] << 1) | 1)) % mod;
                        }
                    }
                    else{
                        if(y || f[i] - '0' == 1){
                            dp[i + 1][j][x][y] = (dp[i + 1][j][x][y] + ((dp[i][j][x][y] << 1) | 1)) % mod;
                        }
                        if(j + 1 <= k){
                            dp[i + 1][j + 1][x ^ 1][y | (0 < f[i] - '0')] = (dp[i + 1][j + 1][x ^ 1][y | (0 < f[i] - '0')] + (dp[i][j][x][y] << 1)) % mod;
                        }
                    }
                }
            }
        }
    }
    if(mst){
        return (dp[n][k][0][1] + dp[n][k][1][1]) % mod;
    }
    return (dp[n][k][0][1] + dp[n][k][1][1] + dp[n][k][0][0] + dp[n][k][1][0]) % mod;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k; --n;
    cin >> s;
    string a, b; cin >> a >> b;
    cout << (sol(b, 0) - sol(a, 1) + mod + (n >= 3)) % mod;
    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 61.0

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