oj.uz

Submission #527830

# Submission time Handle Problem Language Result Execution time Memory
527830 2022-02-18T13:11:20 Z boris_mihov Long puzzle (innopolis2021_final_D) C++14
0 / 100
 439 ms 933128 KB 
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#define int long long

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 < -n/2 || balance > n/2 || len > l) return 0;
    if (ix == n+1) return (len == l && balance == 0 && begin && end);
    if (dp[ix][len][balance + maxn/2][begin][end] != -1) return dp[ix][len][balance + maxn/2][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 + maxn/2][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 + maxn/2][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, 0, 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 439 ms 933028 KB Output is correct
2 Incorrect 363 ms 933092 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 933028 KB Output is correct
2 Incorrect 363 ms 933092 KB Output isn't correct
3 Halted 0 ms 0 KB -