Submission #1305406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305406		peteza	Zapina (COCI20_zapina)	C++20	110 / 110	111 ms	3372 KiB

zapina

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;

int n;
ll dp[355][355][2];
ll ck[355][355];

ll cnk(int a, int b) {
	return ck[a][b];
}

int main() {
	// your code goes here
	for(int i=0;i<355;i++) {
		ck[i][0] = 1;
		for(int j=1;j<=i;j++) {
			ck[i][j] = ck[i-1][j] + ck[i-1][j-1];
			ck[i][j] %= mod;
		}
	}
	cin >> n;
	//memset(dp, -1, sizeof dp);
	memset(dp, 0, sizeof dp);
	dp[0][0][0]=1;
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=n;j++) {
			for(int k=0;k<=j;k++) {
				if(j-k==i) {
					dp[i][j][1] += dp[i-1][k][0]*cnk(n-k, j-k);
					dp[i][j][1] += dp[i-1][k][1]*cnk(n-k, j-k);
					//dp[i][j][1] %= mod;
				} else {
					dp[i][j][0] += dp[i-1][k][0]*cnk(n-k, j-k);
					dp[i][j][1] += dp[i-1][k][1]*cnk(n-k, j-k);
					dp[i][j][0] %= mod;
				}
				dp[i][j][1] %= mod;
			}
		}
	}
	cout << dp[n][n][1];
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55