oj.uz

Submission #52831

# Submission time Handle Problem Language Result Execution time Memory
52831 2018-06-27T04:34:46 Z 윤교준(#1384) Kangaroo (CEOI16_kangaroo) C++11
0 / 100
 3 ms 484 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 2005;
const int MOD = 1000000007;

int dp[MAXN][MAXN][2][2];

int N, CS, CF;

void add(int &a, ll b) {
	a = (b + a) % MOD;
}

int main() {
	cin >> N >> CS >> CF;
	if(2 == N) {
		puts("1");
		return 0;
	}

	dp[0][2][0][0] = 1;

	for(int i = 1; i <= N; i++) {
		if(i == CS || i == CF) {
			for(int j = 1; j <= N; j++) {
				for(int k = 0; k < 4; k++) {
					dp[i][j][k&1][!!(k&2)] = dp[i-1][j][k&1][!!(k&2)];
				}
			}
			continue;
		}
		for(int j = 2; j <= N; j++) {
			for(int k0 = 0; k0 < 2; k0++) {
				for(int k1 = 0; k1 < 2; k1++) {
					ll ret = dp[i-1][j][k0][k1];
					if(!ret) continue;
					//printf("%d %d %d %d : %lld\n", i, j, k0, k1, ret);

					// glue mid
					if(2 < j) add(dp[i][j][k0][k1], ret * (j-2) * 2);

					// glue left
					if(!k0 && i < CS) add(dp[i][j][1][k1], ret);

					// glue right
					if(!k1 && i < CF) add(dp[i][j][k0][1], ret);

					// merge mid
					if(3 < j) add(dp[i][j-1][k0][k1], ret * (j-3));
					
					// merge left
					if(2 < j) {
						if(k0 || CS < i)
							add(dp[i][j-1][1][k1], ret);
					}

					// merge right
					if(2 < j) {
						if(k1 || CF < i)
							add(dp[i][j-1][k0][1], ret);
					}

					// add
					add(dp[i][j+1][k0][k1], ret * (j-1));

					// merge both left and right
					if(2 == j && ((i == N) || (i == N-1 && max(CS, CF) == N) || (i == N-2 && CS + CF == N+N-1))) {
						if(k0 || CS < i) {
							if(k1 || CF < i) {
								add(dp[i][1][1][1], ret);
							}
						}
					}
				}
			}
		}
	}

	cout << dp[N][1][1][1] << endl;
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct