Submission #925516

#	Time	Username	Problem	Language	Result	Execution time	Memory
925516		NK_	Zapina (COCI20_zapina)	C++17	110 / 110	289 ms	600 KiB

zapina

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;
using vi = V<int>;

const int MOD = 1e9 + 7;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	auto add = [&](int &x, int y) {
		x += y; if (x >= MOD) x -= MOD;
	};

	auto mul = [&](int &x, int y) {
		x = (x * 1LL * y) % MOD;
	};

	auto POW = [&](int a, int p) {
		int ans = 1;
		for(; p; p /= 2, mul(a, a)) if (p & 1) mul(ans, a);
		return ans;
	};

	auto INV = [&](int a) {
		return POW(a, MOD - 2);
	};

	int N; cin >> N;

	vi F = {1}, IF = {1}; for(int i = 1; i <= N; i++) {
		F.pb(F.back()); mul(F.back(), i);
		IF.pb(INV(F.back()));
	}

	auto nCk = [&](int n, int k) { 
		int ways = F[n]; 
		mul(ways, IF[n - k]); mul(ways, IF[k]); 
		return ways; 
	};

	V<vi> dp(N + 1, vi(2)), ndp(N + 1, vi(2)); // dp[index][left][happy] = # of ways

	dp[N][0] = 1;
	for(int i = 1; i <= N; i++) {
		for(int x = 0; x <= N; x++) for(int h = 0; h < 2; h++) if (dp[x][h]) {

			for(int g = 0; g <= x; g++) {
				int nx = x - g, nh = h | (g == i);

				int ways = dp[x][h]; mul(ways, nCk(x, g));

				// cout << i << " " << x << " " << h << " => " << nx << " " << nh << " => " << ways << endl;

				add(ndp[nx][nh], ways);
			}
		}

		dp.swap(ndp);
		ndp = V<vi>(N + 1, vi(2));
	} 

	cout << dp[0][1] << nl;

	exit(0-0);
}

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