Submission #233247

#	Time	Username	Problem	Language	Result	Execution time	Memory
233247		VEGAnn	Ljetopica (COI19_ljetopica)	C++14	100 / 100	97 ms	32172 KiB

ljetopica

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int md = int(1e9) + 7;
bool way[N];
int n, k, ms[2][N], f[N][2][N][2], cnt[N][2][N][2];
bool bad;

int sub(int x, int y){
    x -= y;
    if (x < 0)
        x += md;
    return x;
}

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

void SUM(int &x, int y){
    x += y;
    if (x >= md)
        x -= md;
}

int calc(int nm, int mx){
    for (int len = 0; len <= n; len++)
    for (int tp = 0; tp < 2; tp++)
    for (int kl = 0; kl <= k; kl++)
    for (int ori = 0; ori < 2; ori++){
        f[len][tp][kl][ori] = 0;
        cnt[len][tp][kl][ori] = -1;
    }

    f[0][1][0][1] = f[0][1][0][0] = 1;
    cnt[0][1][0][1] = cnt[0][1][0][0] = 1;

    for (int len = 0; len < n - 1; len++)
    for (int tp = 0; tp < 2; tp++)
    for (int kl = 0; kl <= k; kl++)
    for (int ori = 0; ori < 2; ori++){
        if (cnt[len][tp][kl][ori] < 0) continue;

        int nw = (way[len + 1] ^ ori);
        int nln = len + 1;
        int nt = tp;
        int ko = kl;
        int no = ori;
        bad = 0;

        if (tp == 1){
            if (ms[nm][len + 1] < nw)
                bad = 1;
            if (ms[nm][len + 1] > nw)
                nt = 0;
        }

        if (!bad){
            SUM(f[nln][nt][ko][no], sum(f[len][tp][kl][ori], f[len][tp][kl][ori]));
            if (nw == 1)
                SUM(f[nln][nt][ko][no], cnt[len][tp][kl][ori]);

            if (cnt[nln][nt][ko][no] < 0)
                cnt[nln][nt][ko][no] = 0;
            SUM(cnt[nln][nt][ko][no], cnt[len][tp][kl][ori]);
        }

        if (kl == k) continue;

        nw = (way[len + 1] ^ ori ^ 1);
        nln = len + 1;
        nt = tp;
        ko = kl + 1;
        no = ori ^ 1;
        bad = 0;

        if (tp == 1){
            if (ms[nm][len + 1] < nw)
                bad = 1;
            if (ms[nm][len + 1] > nw)
                nt = 0;
        }

        if (!bad){
            SUM(f[nln][nt][ko][no], sum(f[len][tp][kl][ori], f[len][tp][kl][ori]));
            if (nw == 1)
                SUM(f[nln][nt][ko][no], cnt[len][tp][kl][ori]);

            if (cnt[nln][nt][ko][no] < 0)
                cnt[nln][nt][ko][no] = 0;
            SUM(cnt[nln][nt][ko][no], cnt[len][tp][kl][ori]);
        }
    }

    int res = 0;

    for (int tp = 0; tp <= mx; tp++)
    for (int ori = 0; ori < 2; ori++)
        SUM(res, f[n - 1][tp][k][ori]);

    return res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    for (int i = 1; i < n; i++){
        char c; cin >> c;
        way[i] = bool(c == 'R');
    }

    for (int i = 0; i < n; i++){
        char c; cin >> c;
        ms[0][i] = bool(c == '1');
    }

    for (int i = 0; i < n; i++){
        char c; cin >> c;
        ms[1][i] = bool(c == '1');
    }

    cout << sub(calc(1, 1), calc(0, 0));

    return 0;
}

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