Submission #201446

#	Time	Username	Problem	Language	Result	Execution time	Memory
201446		ami	Zapina (COCI20_zapina)	C++17	110 / 110	280 ms	1912 KiB

zapina

#include <bits/stdc++.h>
#define sz(c)       int(c.size())
#define rep(i,a,b)  for (int i=a; i<(b); ++i)
#define per(i,a,b)  for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
typedef long long ll;

int const MD=1000000007;

int madd(int x,int y) {
	if (x+y<MD) return x+y; else return x+y-MD;
}
void minc(int &x,int y) {
	x+=y;
	if (x>=MD) x-=MD;
}
int mmul(int x,int y) {
	return int(ll(x)*y % MD);
}


int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	int N;
	cin>>N;

	vector<vector<int>> comb(N+1,vector<int>(N+1));
	rep(i,0,N+1) {
		comb[i][0]=1;
		rep(j,1,i+1) comb[i][j]=madd(comb[i-1][j],comb[i-1][j-1]);
	}

	vector<vector<array<int,2>>> cnt(N+1,vector<array<int,2>>(N+1));
	cnt[0][N][0]=1;
	rep(i,0,N) rep(j,0,N+1) rep(k,0,2) if (cnt[i][j][k]) {
		rep(l,0,j+1) {
			minc(cnt[i+1][j-l][k||(l==i+1)],mmul(cnt[i][j][k],comb[j][l]));
		}
	}

	cout<<cnt[N][0][1]<<'\n';
}

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