Submission #558617

#	Time	Username	Problem	Language	Result	Execution time	Memory
558617		Yazan_Alattar	Ljetopica (COI19_ljetopica)	C++14	100 / 100	151 ms	69812 KiB

ljetopica

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 3007;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

ll n, k, dp[M][M][2][2], dp2[M][M][2][2];
string s, a, b;

ll solve(string x){
    for(int i = 0; i <= n; ++i) for(int j = 0; j <= k; ++j) for(int Smaller : {0, 1}) for(int flip : {0, 1}) dp[i][j][Smaller][flip] = dp2[i][j][Smaller][flip] = 0;

    dp[0][0][x[0] == '0'][0] = dp[0][0][x[0] == '0'][1] = 1;
    dp2[0][0][x[0] == '0'][0] = dp2[0][0][x[0] == '0'][1] = 1;

    for(int i = 0; i < n - 1; ++i){
        for(int j = 0; j <= k; ++j){
            for(int flip : {0, 1}){
                ll on = (s[i + 1] - '0') ^ flip;
                bool isSmaller1 = (x[i + 1] == '1' && on == 0);
                bool isSmaller2 = (x[i + 1] == '1' && on);

                dp[i + 1][j][1][flip] = (dp[i + 1][j][1][flip] + dp[i][j][1][flip]) % mod;
                dp[i + 1][j + 1][1][!flip] = (dp[i + 1][j + 1][1][!flip] + dp[i][j][1][flip]) % mod;

                dp2[i + 1][j][1][flip] = (dp2[i + 1][j][1][flip] + 2 * dp2[i][j][1][flip] + dp[i][j][1][flip] * on) % mod;
                dp2[i + 1][j + 1][1][!flip] = (dp2[i + 1][j + 1][1][!flip] + 2 * dp2[i][j][1][flip] + dp[i][j][1][flip] * !on) % mod;


                if(x[i + 1] == '1' || !on) dp[i + 1][j][isSmaller1][flip] = (dp[i + 1][j][isSmaller1][flip] + dp[i][j][0][flip]) % mod;
                if(x[i + 1] == '1' || on) dp[i + 1][j + 1][isSmaller2][!flip] = (dp[i + 1][j + 1][isSmaller2][!flip] + dp[i][j][0][flip]) % mod;

                if(x[i + 1] == '1' || !on) dp2[i + 1][j][isSmaller1][flip] = (dp2[i + 1][j][isSmaller1][flip] + 2 * dp2[i][j][0][flip] + dp[i][j][0][flip] * on) % mod;
                if(x[i + 1] == '1' || on) dp2[i + 1][j + 1][isSmaller2][!flip] = (dp2[i + 1][j + 1][isSmaller2][!flip] + 2 * dp2[i][j][0][flip] + dp[i][j][0][flip] * !on) % mod;
            }
        }
    }

    ll ret = 0;
    for(int i : {0, 1})
        for(int j : {0, 1})
            ret = (ret + dp2[n - 1][k][i][j]) % mod;

    return ret;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k >> s >> a >> b;
    s = '#' + s;
    for(int i = 1; i < n; ++i){
        if(s[i] == 'L') s[i] = '0';
        else s[i] = '1';
    }

    for(int i = n - 1; i >= 0; --i){
        if(a[i] == '0') a[i] = '1';
        else{
            a[i] = '0';
            break;
        }
    }

    cout << (solve(b) - solve(a) + mod) % mod;
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61