Submission #527834

#	Time	Username	Problem	Language	Result	Execution time	Memory
527834		boris_mihov	Long puzzle (innopolis2021_final_D)	C++14	0 / 100	184 ms	466692 KiB

Main

#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>

const int maxn = 300 + 10, mod = 1e9+7;

int n, l;
int size[maxn];
std::pair < int, int > p[maxn];

int dp[maxn][maxn][maxn][2][2];
int f(int ix, int len, int balance, bool begin, bool end) {

    if (balance < 0 || balance >= maxn || len > l) return 0;
    if (ix == n+1) return (len == l && balance == maxn/2 && begin && end);
    if (dp[ix][len][balance][begin][end] != -1) return dp[ix][len][balance][begin][end];

    int res = f(ix+1, len, balance, begin, end);
    
    if ((begin && (p[ix].first == 0)) || (end && (p[ix].second == 0))) return dp[ix][len][balance][begin][end] = res;
    
    int new_bal = balance;
    if (p[ix].first == 1) ++new_bal;
    if (p[ix].second == 1) --new_bal;

    res += f(ix+1, len + size[ix], new_bal, begin || (p[ix].first == 0), end || (p[ix].second == 0));
    if (res >= mod) res -= mod;

    return dp[ix][len][balance][begin][end] = res;

}

std::string front, back;
void read() {

    std::cin >> n >> l;
    for (int i = 1 ; i <= n ; ++i) {

        std::cin >> size[i] >> front >> back;
        
        if (front == "none") p[i].first = 0;
        if (front == "in") p[i].first = 1;
        if (front == "out") p[i].first = 2;

        if (back == "none") p[i].second = 0;
        if (back == "out") p[i].second = 1;
        if (back == "in") p[i].second = 2;

    }

    memset(dp, -1, sizeof(dp));
    std::cout << f(1, 0, maxn/2, 0, 0) << '\n';

}

void fast_io() {

    std::ios_base :: sync_with_stdio(0);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

}

signed main () {

    fast_io();
    read();

    return 0;

}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20