oj.uz

Submission #611697

# Submission time Handle Problem Language Result Execution time Memory
611697 2022-07-29T06:40:52 Z 이동현(#8500) Ljetopica (COI19_ljetopica) C++17
8 / 100
 46 ms 31888 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 cnt[1004][1004][2][2];

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

                    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) + cnt[i][j][x][y])) % 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) + cnt[i][j][x][y])) % 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) % mod;
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31828 KB Output is correct
2 Correct 17 ms 31880 KB Output is correct
3 Correct 16 ms 31876 KB Output is correct
4 Correct 18 ms 31792 KB Output is correct
5 Correct 16 ms 31868 KB Output is correct
6 Correct 17 ms 31888 KB Output is correct
7 Correct 17 ms 31832 KB Output is correct
8 Correct 18 ms 31880 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31828 KB Output is correct
2 Correct 17 ms 31880 KB Output is correct
3 Correct 16 ms 31876 KB Output is correct
4 Correct 18 ms 31792 KB Output is correct
5 Correct 16 ms 31868 KB Output is correct
6 Correct 17 ms 31888 KB Output is correct
7 Correct 17 ms 31832 KB Output is correct
8 Correct 18 ms 31880 KB Output is correct
9 Incorrect 16 ms 31828 KB Output isn't correct
10 Halted 0 ms 0 KB -