Submission #985342

#	Time	Username	Problem	Language	Result	Execution time	Memory
985342		Nalrimet	Ljetopica (COI19_ljetopica)	C++17	0 / 100	166 ms	85848 KiB

ljetopica

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MOD = 1000000007;

int bin_to_int(const string &bin) {
    int value = 0;
    for (char c : bin) {
        value = value * 2 + (c - '0');
    }
    return value;
}

int add_mod(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

int calculate_sum(int N, int K, const string &path, int max_value) {
    vector<vector<vector<vector<int>>>> dp(N, vector<vector<vector<int>>>(K+1, vector<vector<int>>(2, vector<int>(2, 0))));
    
    dp[0][0][0][0] = 1; // Initial state

    for (int i = 0; i < N-1; ++i) {
        for (int k = 0; k <= K; ++k) {
            for (int smaller = 0; smaller < 2; ++smaller) {
                for (int last = 0; last < 2; ++last) {
                    if (dp[i][k][smaller][last] == 0) continue;

                    for (int move = 0; move < 2; ++move) {
                        int new_smaller = smaller;
                        if (move == 1 && (max_value & (1 << (N-2-i))) == 0) {
                            new_smaller = 1;
                        }
                        if (move == 0 && (max_value & (1 << (N-2-i))) != 0) {
                            new_smaller = 1;
                        }

                        if (path[i] == 'L' && last == 0 || path[i] == 'R' && last == 1) {
                            dp[i+1][k][new_smaller][0] = add_mod(dp[i+1][k][new_smaller][0], dp[i][k][smaller][last]);
                        } else {
                            dp[i+1][k][new_smaller][1] = add_mod(dp[i+1][k][new_smaller][1], dp[i][k][smaller][last]);
                        }
                        if (k < K) {
                            if (path[i] == 'L' && last == 1 || path[i] == 'R' && last == 0) {
                                dp[i+1][k+1][new_smaller][0] = add_mod(dp[i+1][k+1][new_smaller][0], dp[i][k][smaller][last]);
                            } else {
                                dp[i+1][k+1][new_smaller][1] = add_mod(dp[i+1][k+1][new_smaller][1], dp[i][k][smaller][last]);
                            }
                        }
                    }
                }
            }
        }
    }

    int sum = 0;
    for (int k = 0; k <= K; ++k) {
        for (int smaller = 0; smaller < 2; ++smaller) {
            for (int last = 0; last < 2; ++last) {
                sum = add_mod(sum, dp[N-1][k][smaller][last]);
            }
        }
    }

    return sum;
}

int main() {
    int N, K;
    cin >> N >> K;
    string path;
    cin >> path;
    string binA, binB;
    cin >> binA >> binB;
    
    int A = bin_to_int(binA);
    int B = bin_to_int(binB);

    int sumB = calculate_sum(N, K, path, B);
    int sumA_minus_1 = calculate_sum(N, K, path, A - 1);

    int result = (sumB - sumA_minus_1 + MOD) % MOD;
    cout << result << endl;

    return 0;
}

Compilation message (stderr)

ljetopica.cpp: In function 'int calculate_sum(int, int, const string&, int)':
ljetopica.cpp:42:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |                         if (path[i] == 'L' && last == 0 || path[i] == 'R' && last == 1) {
ljetopica.cpp:48:48: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |                             if (path[i] == 'L' && last == 1 || path[i] == 'R' && last == 0) {

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