Submission #465714

#	Time	Username	Problem	Language	Result	Execution time	Memory
465714		SirCovidThe19th	Ljetopica (COI19_ljetopica)	C++17	100 / 100	124 ms	16160 KiB

ljetopica

#include <bits/stdc++.h>
using namespace std; 

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define ad(x, y) x = ((x) + (y)) % md

const int mx = 1005, md = 1e9 + 7;

int n, k, mv[mx]; bitset<mx> A, B;

int solve(bitset<mx> X){
    bool cover[mx] = {}; int sum[mx][mx][2] = {}, cnt[mx][mx][2] = {};

    for (int i = n - 1; i >= 0, cover[i] = 1, X[n - i - 1]; i--);

    sum[0][0][!cover[0]] = cnt[0][0][!cover[0]] = 1;
    
    X <<= 1;
    FOR(i, 0, n - 1) FOR(j, 0, k + 1){
        int f = j % 2, L = !(mv[i] ^ f), R = 1 - L;

        ad(sum[i + 1][j + R][0], sum[i][j][0] * 2LL);
        ad(sum[i + 1][j + L][0], sum[i][j][0] * 2LL + cnt[i][j][0]);

        ad(cnt[i + 1][j][0], cnt[i][j][0]);
        ad(cnt[i + 1][j + 1][0], cnt[i][j][0]);

        int tight = !X[n - i - 1] and !cover[i + 1];
        ad(sum[i + 1][j + R][tight], sum[i][j][1] * 2LL);
        ad(cnt[i + 1][j + R][tight], cnt[i][j][1]);

        if (X[n - i - 1]){
            ad(sum[i + 1][j + L][1], sum[i][j][1] * 2LL + cnt[i][j][1]);
            ad(cnt[i + 1][j + L][1], cnt[i][j][1]);
        }
    }
    return sum[n - 1][k][0];
}


int main(){
    cin >> n >> k;
    FOR(i, 0, n - 1){ char c; cin >> c; mv[i] = c == 'R'; }
    cin >> A >> B;
    for (int i = 0; i < n; i++){ 
        if (A[i]){ A[i] = 0; break; } 
        else A[i] = 1;
    }
    int res1 = solve(B); if (A[n - 1]) res1 -= solve(A);
    FOR(i, 0, n - 1) mv[i] ^= 1;
    int res2 = solve(B); if (A[n - 1]) res2 -= solve(A);
    cout<<((long long)res1 + res2 + 2 * md) % md<<endl;
}

Compilation message (stderr)

ljetopica.cpp: In function 'int solve(std::bitset<1005>)':
ljetopica.cpp:14:27: warning: left operand of comma operator has no effect [-Wunused-value]
   14 |     for (int i = n - 1; i >= 0, cover[i] = 1, X[n - i - 1]; i--);
      |                         ~~^~~~

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