Submission #234433

# Submission time Handle Problem Language Result Execution time Memory
234433 2020-05-24T08:44:47 Z oolimry Tents (JOI18_tents) C++14
100 / 100
237 ms 71288 KB
#include <bits/stdc++.h>
#define int long long
using namespace std;

int memo[3005][3005];

const int mod = 1000000007;
int dp(int H, int W){ ///ways such that the topmost row and rightmost column are occupied
	if(W < 0 || W < 0) return 0;
	if(W == 0 || H == 0) return 1;
	if(memo[H][W]  != -1) return memo[H][W];
	
	int ans = 0;
	if(H == 1){
		ans = 4*W + 1;
		ans += (W-1)*W/2;
		return ans;
	}
	
	///new row is empty
	ans += dp(H-1,W);
	
	///new row is 1 thing facing nothing
	ans += 4*dp(H-1,W-1)*W;
	
	///new row is 2 things facing each other
	ans += dp(H-1,W-2) * (W) * (W-1) / 2;
	
	///new row is south, and north is somwhere below
	ans += dp(H-2, W-1) * W * (H-1);
	
	ans %= mod;
	memo[H][W] = ans;
	return ans;
}

signed main(){	
	int H, W; cin >> H >> W;
	memset(memo, -1, sizeof(memo));
	
	int ans = dp(H,W);
	ans--;
	if(ans < 0) ans += mod;
	cout << ans;
}
# Verdict Execution time Memory Grader output
1 Correct 42 ms 71032 KB Output is correct
2 Correct 39 ms 71032 KB Output is correct
3 Correct 39 ms 71032 KB Output is correct
4 Correct 38 ms 71032 KB Output is correct
5 Correct 39 ms 71032 KB Output is correct
6 Correct 39 ms 71032 KB Output is correct
7 Correct 43 ms 71160 KB Output is correct
8 Correct 40 ms 71032 KB Output is correct
9 Correct 39 ms 71032 KB Output is correct
10 Correct 43 ms 71036 KB Output is correct
11 Correct 39 ms 71032 KB Output is correct
12 Correct 41 ms 71032 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 42 ms 71032 KB Output is correct
2 Correct 39 ms 71032 KB Output is correct
3 Correct 39 ms 71032 KB Output is correct
4 Correct 38 ms 71032 KB Output is correct
5 Correct 39 ms 71032 KB Output is correct
6 Correct 39 ms 71032 KB Output is correct
7 Correct 43 ms 71160 KB Output is correct
8 Correct 40 ms 71032 KB Output is correct
9 Correct 39 ms 71032 KB Output is correct
10 Correct 43 ms 71036 KB Output is correct
11 Correct 39 ms 71032 KB Output is correct
12 Correct 41 ms 71032 KB Output is correct
13 Correct 44 ms 71004 KB Output is correct
14 Correct 40 ms 71168 KB Output is correct
15 Correct 182 ms 71168 KB Output is correct
16 Correct 42 ms 71040 KB Output is correct
17 Correct 53 ms 71032 KB Output is correct
18 Correct 68 ms 71160 KB Output is correct
19 Correct 196 ms 71160 KB Output is correct
20 Correct 162 ms 71160 KB Output is correct
21 Correct 108 ms 71160 KB Output is correct
22 Correct 118 ms 71168 KB Output is correct
23 Correct 78 ms 71288 KB Output is correct
24 Correct 237 ms 71160 KB Output is correct
25 Correct 189 ms 71168 KB Output is correct
26 Correct 211 ms 71228 KB Output is correct
27 Correct 223 ms 71160 KB Output is correct