Submission #333480

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333480	2020-12-06T08:31:06 Z	benson1029	Tents (JOI18_tents)	C++14	48 / 100	112 ms	63084 KB

tents

#include<bits/stdc++.h>
#define MOD ((long long)1e9+7)
using namespace std;
int n,m;
long long dp[3005][3005];
int main() {
	cin >> n >> m;
	dp[0][0] = 1LL;
	for(int i=0; i<n; i++) {
		for(int j=0; j<=m; j++) {
			if(j+2<=m) {
				dp[i+1][j+2] += (((m-j)*(m-j-1LL)/2)%MOD) * dp[i][j];
				dp[i+1][j+2] %= MOD;
			}
			if(j<m) {
				dp[i+1][j+1] += dp[i][j] * (m-j) * 4LL;
				dp[i+1][j+1] %= MOD;
			}
			if(i<n-1) {
				dp[i+2][j+1] += dp[i][j] * (((long long)m-j)*(i+1))%MOD;
			}
		}
		for(int j=0; j<=m; j++) {
			dp[i+1][j] += dp[i][j];
		}
	}
	long long ans = 0;
	for(int j=1; j<=m; j++) {
		ans += dp[n][j];
	}
	cout << ans%MOD << endl;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	1132 KB	Output is correct
5	Correct	1 ms	748 KB	Output is correct
6	Correct	1 ms	1388 KB	Output is correct
7	Correct	1 ms	876 KB	Output is correct
8	Correct	1 ms	1516 KB	Output is correct
9	Correct	1 ms	896 KB	Output is correct
10	Correct	2 ms	1772 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	3 ms	2284 KB	Output is correct

Subtask #2

0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	1132 KB	Output is correct
5	Correct	1 ms	748 KB	Output is correct
6	Correct	1 ms	1388 KB	Output is correct
7	Correct	1 ms	876 KB	Output is correct
8	Correct	1 ms	1516 KB	Output is correct
9	Correct	1 ms	896 KB	Output is correct
10	Correct	2 ms	1772 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	3 ms	2284 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	6 ms	9708 KB	Output is correct
15	Correct	105 ms	55240 KB	Output is correct
16	Correct	7 ms	4076 KB	Output is correct
17	Correct	25 ms	12928 KB	Output is correct
18	Correct	28 ms	17132 KB	Output is correct
19	Incorrect	112 ms	63084 KB	Output isn't correct
20	Halted	0 ms	0 KB	-