Submission #255183

#	Time	Username	Problem	Language	Result	Execution time	Memory
255183		shayan_p	parentrises (BOI18_parentrises)	C++14	50 / 100	158 ms	115320 KiB

parentrises

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

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

int dp[maxn][2 * maxn][maxn]; // n // 2o - c // o - 2c
int ans[maxn];
	     
void add(int &A, int B){
    A = (A + B) % mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int P;
    cin >> P;
    assert(P == 2);

    dp[0][0][0] = 1;
    for(int n = 0; n < maxn - 5; n++){
	for(int sm = 0; sm <= 2 * n; sm++){
	    for(int mx = 0; mx <= n; mx++){
		add(dp[n + 1][sm + 2][max(int(0), mx + 1)], dp[n][sm][mx]);
		if(sm > 0)
		    add(dp[n+1][sm - 1][max(int(0), mx - 2)], dp[n][sm][mx]);
	    }
	    add(ans[n], dp[n][sm][0]);
	}
    }
    
    int q;
    cin >> q;
    while(q--){
	int n;
	cin >> n;
	cout << ans[n] << "\n";
    }

    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