Submission #220224

#	Time	Username	Problem	Language	Result	Execution time	Memory
220224		atoiz	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	494 ms	8960 KiB

ruins3

/*input
10
5 8 9 13 15 16 17 18 19 20
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORB(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 607, MOD = 1e9 + 7, HALF = (MOD + 1) / 2;
int N, F[MAXN * 2][MAXN], G[2][MAXN][MAXN], H[MAXN], C[MAXN * 2][MAXN * 2];
bool alive[MAXN * 2];

int add(int x, int y)
{ return x -= ((x += y) >= MOD ? MOD : 0); }

int sub(int x, int y)
{ return x += ((x -= y) < 0 ? MOD : 0); }

int mul(int x, int y)
{ return int(1ll * x * y % MOD); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	FOR(_, 0, N - 1) {
		int x;
		cin >> x;
		alive[x] = 1;
	}

	FOR(i, 0, MAXN) C[i][0] = 1;
	FOR(i, 1, MAXN) FOR(j, 1, i) C[i][j] = add(C[i - 1][j - 1], C[i - 1][j]);

	G[0][0][0] = 1;
	FOR(i, 1, N) {
		FOR(c2, 0, i / 2) FOR(c1, 0, i - 2 * c2) {
			G[i & 1][c1][c2] = 0;
			if (c1 + c2 * 2 <= i - 1) G[i & 1][c1][c2] = add(G[i & 1][c1][c2], mul(HALF, G[(i - 1) & 1][c1][c2]));
			if (c1 > 0) G[i & 1][c1][c2] = add(G[i & 1][c1][c2], mul(G[(i - 1) & 1][c1 - 1][c2], C[c1 + c2 * 2][1]));
			if (c2 > 0) G[i & 1][c1][c2] = add(G[i & 1][c1][c2], mul(G[(i - 1) & 1][c1][c2 - 1], C[c1 + c2 * 2][2]));

			if (c1 + c2 * 2 == i - 1) {
				// cout << "g " << i - 1 << ' ' << c1 << ' ' << c2 << ": " << G[(i - 1) & 1][c1][c2] << endl;
				int c0 = i - c1 - c2;
				int mult = add(c0, mul(c1, HALF));
				H[i] = add(H[i], mul(mult, G[(i - 1) & 1][c1][c2]));
			}
		}
	}
	// FOR(i, 1, N) cout << H[i] << " \n"[i == N];

	F[2 * N + 1][0] = 1;
	int num_dead = 0, num_alive = 0;
	for (int i = 2 * N; i >= 1; --i) {
		for (int j = 0; j <= num_alive + alive[i]; ++j) {
			if (alive[i]) {
				F[i][j] = F[i + 1][j];
				for (int k = 0; k < j; ++k) {
					F[i][j] = add(F[i][j], mul(F[i + 1][k], mul(C[num_alive - k][j - k - 1], H[j - k])));
				}
			} else {
				if (num_dead >= j) continue;
				F[i][j] = mul(F[i + 1][j], j - num_dead);
			}
		}

		if (alive[i]) ++num_alive;
		else ++num_dead;
	}

	cout << F[1][N] << endl;
}

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42