Submission #96608

#	Time	Username	Problem	Language	Result	Execution time	Memory
96608		josiftepe	parentrises (BOI18_parentrises)	C++14	50 / 100	213 ms	111464 KiB

parentrises

#include <bits/stdc++.h>

using namespace std;
int dp[305][305][305];
const int MOD = 1e9 + 7;
int rek(int at, int open, int closed){
    if(at == 0){
        if(closed == 0){
            return 1;
        }
        return 0;
    }
    if(dp[at][open][closed] != -1){
        return dp[at][open][closed];
    }
    int ret = 0;
    ret += rek(at - 1, open + 2, closed + 1);
    if(open > 0){
        ret += rek(at - 1, open - 1, max(closed - 2, 0));
    }
    return dp[at][open][closed] = ret % MOD;
}
int n;
int main()
{
    ios_base::sync_with_stdio(false);
    int t_case;
    cin >> t_case;
    int t;
    cin >> t;
    memset(dp, -1, sizeof dp);
    while(t --){
        cin >> n;
        cout << rek(n, 0, 0) << endl;
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 6
• Subtask 4: 0 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28