oj.uz

Submission #527837

# Submission time Handle Problem Language Result Execution time Memory
527837 2022-02-18T13:16:31 Z boris_mihov Long puzzle (innopolis2021_final_D) C++14
0 / 100
 342 ms 933040 KB 
#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][2*maxn][2][2];
int f(int ix, int len, int balance, bool begin, bool end) {

    if (balance < 0 || balance >= 2*maxn || len > l) return 0;
    if (ix == n+1) return (len == l && balance == maxn && 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, 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.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 933040 KB Output is correct
2 Incorrect 342 ms 932964 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 342 ms 933036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 334 ms 932984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 334 ms 932984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 933040 KB Output is correct
2 Incorrect 342 ms 932964 KB Output isn't correct
3 Halted 0 ms 0 KB -