Submission #670930

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670930	2022-12-11T10:47:52 Z	Makarooni	Tents (JOI18_tents)	C++14	100 / 100	184 ms	117488 KB

tents

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb(x) push_back(x)
#define mr(x, y) make_pair(x, y)
#define sz(x) (int)x.size()
#define S second
#define F first

const int N = 3e3 + 10;
const int MOD = 1e9 + 7;

long long dp[N][N], c[N][N], fact[N], pw[N];

int main(){
    int h, w;
    cin >> h >> w;
    pw[0] = 1;
    fact[0] = 1;
    for(int i = 0; i < N; i++)
    	c[i][0] = 1;
    for(int i = 1; i < N; i++){
    	fact[i] = fact[i - 1] * i;
    	fact[i] %= MOD;
    	pw[i] = pw[i - 1] * 4;
    	pw[i] %= MOD;
    	for(int j = 1; j <= i; j++){
    		c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
		}
	}
	for(int i = 0; i < N; i++){
		dp[0][i] = 1;
		dp[i][0] = 1;
	}
    for(int i = 1; i <= h; i++){
    	for(int j = 1; j <= w; j++){
				dp[i][j] += dp[i - 1][j];
					dp[i][j] %= MOD;
					if(j >= 2)
						dp[i][j] += c[j][2] * dp[i - 1][j - 2];
					dp[i][j] %= MOD;
					if(i >= 2)
						dp[i][j] += j * (i - 1) * dp[i - 2][j - 1];
					dp[i][j] %= MOD;
		}
	}
	long long ans = 0;
	for(int k = 1; k <= min(h, w); k++){
		ans += ((((((c[h][k] * c[w][k]) % MOD) * fact[k]) % MOD) * dp[h - k][w - k]) % MOD) * pw[k];
		ans %= MOD;
	}
	ans += dp[h][w];
	ans %= MOD;
	if(ans == 0)
        cout << MOD - 1;
    else
        cout << ans - 1;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	58956 KB	Output is correct
2	Correct	28 ms	58992 KB	Output is correct
3	Correct	27 ms	59056 KB	Output is correct
4	Correct	26 ms	58968 KB	Output is correct
5	Correct	29 ms	59136 KB	Output is correct
6	Correct	28 ms	59144 KB	Output is correct
7	Correct	28 ms	59204 KB	Output is correct
8	Correct	28 ms	59092 KB	Output is correct
9	Correct	29 ms	59048 KB	Output is correct
10	Correct	28 ms	59332 KB	Output is correct
11	Correct	27 ms	59092 KB	Output is correct
12	Correct	29 ms	59744 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	58956 KB	Output is correct
2	Correct	28 ms	58992 KB	Output is correct
3	Correct	27 ms	59056 KB	Output is correct
4	Correct	26 ms	58968 KB	Output is correct
5	Correct	29 ms	59136 KB	Output is correct
6	Correct	28 ms	59144 KB	Output is correct
7	Correct	28 ms	59204 KB	Output is correct
8	Correct	28 ms	59092 KB	Output is correct
9	Correct	29 ms	59048 KB	Output is correct
10	Correct	28 ms	59332 KB	Output is correct
11	Correct	27 ms	59092 KB	Output is correct
12	Correct	29 ms	59744 KB	Output is correct
13	Correct	28 ms	58956 KB	Output is correct
14	Correct	28 ms	58996 KB	Output is correct
15	Correct	120 ms	102648 KB	Output is correct
16	Correct	33 ms	61824 KB	Output is correct
17	Correct	48 ms	68684 KB	Output is correct
18	Correct	47 ms	71136 KB	Output is correct
19	Correct	142 ms	109964 KB	Output is correct
20	Correct	129 ms	99716 KB	Output is correct
21	Correct	84 ms	85808 KB	Output is correct
22	Correct	77 ms	85368 KB	Output is correct
23	Correct	45 ms	73680 KB	Output is correct
24	Correct	184 ms	117488 KB	Output is correct
25	Correct	147 ms	109580 KB	Output is correct
26	Correct	161 ms	114016 KB	Output is correct
27	Correct	171 ms	116020 KB	Output is correct