Submission #269711

#	Time	Username	Problem	Language	Result	Execution time	Memory
269711		sebinkim	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	753 ms	13688 KiB

ruins3

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;

ll C[1212][1212], K[666][1212][2], D[666], B[666];
bool A[1212];
ll n, s;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll i, j, l, c0, c1;

	cin >> n;

	for(i = C[0][0] = 1; i <= n; i ++){
		for(j = C[i][0] = 1; j <= n; j ++){
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
		}
	}

	K[0][0][0] = 1;
	for(i = 1; i <= n; i ++){
		c0 = c1 = 0;
		for(j = 1; j <= n + n; j ++){
			c0 = (c0 + K[i - 1][j - 1][0]) % mod;
			if(j > i + i) K[i][j][0] = c0 * i % mod;

			c1 = (c1 + K[i - 1][j - 1][1]) % mod;
			if(j >= i + i - 1) K[i][j][1] = (c0 + c1 * (i - 1)) % mod;
		}
		B[i] = (K[i][i + i - 1][1] + K[i][i + i][1]) % mod;
	}

	for(i = 1; i <= n; i ++){
		cin >> j; A[j] = 1;
	}

	D[0] = 1;
	for(i = n + n, c0 = c1 = 0; i >= 1; i --){
		if(A[i] == 1){
			for(j = n; j >= 0; j --){
				for(l = 0; l < j; l ++){
					D[j] = (D[j] + D[l] * C[c1 - l][j - l - 1] % mod
						* B[j - l]) % mod;
				}
			}
			c1 ++;
		}
		else{
			for(j = 0; j <= n; j ++){
				D[j] = D[j] * (j - c0) % mod;
			}
			c0 ++;
		}
	}

	s = D[n];
	for(i = 1; i <= n; i ++){
		s = s * (mod + 1 >> 1) % mod;
	}

	cout << s << "\n";

	return 0;
}

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:65:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   s = s * (mod + 1 >> 1) % mod;
      |            ~~~~^~~

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