Submission #775135

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
775135	2023-07-06T08:07:53 Z	박상훈(#9985)	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	51 / 100	1875 ms	70240 KB

festival2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, MOD;
ll dp[2][606][606][2][3];
ll dp2[2][606];

inline void add(ll &x, const ll &y){
	x += y;
	if (x>=MOD) x -= MOD;
}

int main(){
	scanf("%d %d", &n, &MOD);

	dp[0][0][0][0][0] = 1;
	dp2[0][0] = 1;

	for (int i=1;i<=n*2;i++){
		int z = i&1;

		for (int j=0;j<=i;j++){
			for (int k=0;k<=i;k++){
				dp[z][j][k][0][0] = 0;
				dp[z][j][k][0][1] = 0;
				dp[z][j][k][0][2] = 0;
				dp[z][j][k][1][0] = 0;
				dp[z][j][k][1][1] = 0;
				dp[z][j][k][1][2] = 0;
			}

			dp2[z][j] = 0;
		}

		for (int j=0;j<i;j++){
			add(dp2[z][j+1], dp2[z^1][j]);
			if (j) add(dp2[z][j-1], dp2[z^1][j] * j % MOD);
		}

		for (int j=0;j<i;j++){ // j개 열림
			for (int k=0;k<=j;k++){ // k개 후보
				// 열기
				add(dp[z][j+1][k+1][0][2], dp[z^1][j][k][0][0]);
				add(dp[z][j+1][k+1][1][2], dp[z^1][j][k][1][0]);

				add(dp[z][j+1][k+1][0][1], dp[z^1][j][k][0][1]);
				add(dp[z][j+1][k+1][1][1], dp[z^1][j][k][1][1]);
				add(dp[z][j+1][k+1][0][2], dp[z^1][j][k][0][2]);
				add(dp[z][j+1][k+1][1][2], dp[z^1][j][k][1][2]);

				// 닫기
				// 후보 x 시작그리디 x
				if (j > k){
					add(dp[z][j-1][k][0][0], dp[z^1][j][k][0][0] * (j-k) % MOD);
					add(dp[z][j-1][k][1][0], dp[z^1][j][k][1][0] * (j-k) % MOD);

					add(dp[z][j-1][k][0][2], dp[z^1][j][k][0][2] * (j-k) % MOD);
					add(dp[z][j-1][k][1][2], dp[z^1][j][k][1][2] * (j-k) % MOD);

					if (j-k > 1){
						add(dp[z][j-1][k][0][1], dp[z^1][j][k][0][1] * (j-k-1) % MOD);
						
						add(dp[z][j-1][k][1][1], dp[z^1][j][k][1][1] * (j-k-1) % MOD);

					}
				} 

				// 시작그리디 o
				if (j){
					// 후보 x
					if (j > k) add(dp[z][j-1][k][0][0], dp[z^1][j][k][1][1]);

					// 후보 o
					if (k){
						add(dp[z][j-1][0][0][0], dp[z^1][j][k][0][2]);
						add(dp[z][j-1][0][1][0], dp[z^1][j][k][1][2]);
					}
				} 

				// 후보 o 시작그리디 x
				if (j && k){
					add(dp[z][j-1][0][1][0], dp[z^1][j][k][0][0] * k % MOD);
					add(dp[z][j-1][0][1][1], dp[z^1][j][k][0][1] * k % MOD);
					add(dp[z][j-1][0][1][1], dp[z^1][j][k][0][2] * (k-1) % MOD);
				}

			}
		}

		// if (i==2) printf("%lld\n", dp[z][0][0][0][0]);
		// if (i==2) printf("%lld\n\n", dp[z][2][2][0][2]);

		// if (i==3) printf("%lld\n", dp[z][1][1][0][2]);
		// if (i==3) printf("%lld\n", dp[z][1][0][0][0]);
		// if (i==3) printf("%lld\n", dp[z][1][0][1][1]);
	}

	// printf("%lld / %lld\n", dp[0][0][0][0][0], dp2[0][0]);

	printf("%lld\n", (dp2[0][0] + MOD - dp[0][0][0][0][0]) % MOD);
}

Compilation message

festival2.cpp: In function 'int main()':
festival2.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d %d", &n, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	440 KB	Output is correct

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	440 KB	Output is correct
14	Correct	1 ms	596 KB	Output is correct
15	Correct	2 ms	1108 KB	Output is correct
16	Correct	2 ms	1076 KB	Output is correct
17	Correct	1 ms	724 KB	Output is correct
18	Correct	1 ms	568 KB	Output is correct

Subtask #4
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	440 KB	Output is correct
14	Correct	1 ms	596 KB	Output is correct
15	Correct	2 ms	1108 KB	Output is correct
16	Correct	2 ms	1076 KB	Output is correct
17	Correct	1 ms	724 KB	Output is correct
18	Correct	1 ms	568 KB	Output is correct
19	Correct	1800 ms	34528 KB	Output is correct
20	Correct	1700 ms	34108 KB	Output is correct
21	Correct	1723 ms	34152 KB	Output is correct
22	Correct	7 ms	1876 KB	Output is correct
23	Correct	59 ms	5520 KB	Output is correct

Subtask #5
0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	440 KB	Output is correct
14	Correct	1 ms	596 KB	Output is correct
15	Correct	2 ms	1108 KB	Output is correct
16	Correct	2 ms	1076 KB	Output is correct
17	Correct	1 ms	724 KB	Output is correct
18	Correct	1 ms	568 KB	Output is correct
19	Correct	1800 ms	34528 KB	Output is correct
20	Correct	1700 ms	34108 KB	Output is correct
21	Correct	1723 ms	34152 KB	Output is correct
22	Correct	7 ms	1876 KB	Output is correct
23	Correct	59 ms	5520 KB	Output is correct
24	Runtime error	1875 ms	70240 KB	Execution killed with signal 11
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	440 KB	Output is correct
14	Correct	1 ms	596 KB	Output is correct
15	Correct	2 ms	1108 KB	Output is correct
16	Correct	2 ms	1076 KB	Output is correct
17	Correct	1 ms	724 KB	Output is correct
18	Correct	1 ms	568 KB	Output is correct
19	Correct	1800 ms	34528 KB	Output is correct
20	Correct	1700 ms	34108 KB	Output is correct
21	Correct	1723 ms	34152 KB	Output is correct
22	Correct	7 ms	1876 KB	Output is correct
23	Correct	59 ms	5520 KB	Output is correct
24	Runtime error	1875 ms	70240 KB	Execution killed with signal 11
25	Halted	0 ms	0 KB	-

Submission #775135

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 27.0 / 27.0

Subtask #4 14.0 / 14.0

Subtask #5 0 / 36.0

Subtask #6 0 / 13.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
27.0 / 27.0

Subtask #4
14.0 / 14.0

Subtask #5
0 / 36.0

Subtask #6
0 / 13.0