Submission #56308

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
56308	2018-07-11T04:17:53 Z	윤교준(#1600)	Tents (JOI18_tents)	C++11	48 / 100	2000 ms	33268 KB

tents

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;
const int MAXH = 3005;
const int MAXW = 3005;

int dp[MAXH][MAXW];

int H, W;

int f(int H, int W) {
	int &ret = dp[H][W];
	if(0 <= ret) return ret;

	ret = 1;
	for(int k = 1; k <= H; k++)
		ret = (ll(f(H-k, W-1)) * W % MOD * 4 + ret) % MOD;
	for(int k = 1; k < H; k++)
		ret = (ll(H-k) * f(H-k-1, W-1) % MOD * W + ret) % MOD;
	for(int k = 1; k <= H; k++)
		ret = (ll(W) * (W-1) / 2 % MOD * f(H-k, W-2) + ret) % MOD;
	return ret;
}

int main() {
	cin >> H >> W;

	for(int i = 0; i <= H; i++) dp[i][0] = 1;
	for(int i = 0; i <= W; i++) dp[0][i] = 1;
	for(int i = 1; i <= H; i++)
		fill(dp[i]+1, dp[i]+W+1, -1);

	cout << (f(H, W) - 1) << endl;
	return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	560 KB	Output is correct
4	Correct	3 ms	1200 KB	Output is correct
5	Correct	5 ms	1200 KB	Output is correct
6	Correct	57 ms	1388 KB	Output is correct
7	Correct	10 ms	1388 KB	Output is correct
8	Correct	42 ms	1664 KB	Output is correct
9	Correct	3 ms	1664 KB	Output is correct
10	Correct	107 ms	1796 KB	Output is correct
11	Correct	2 ms	1796 KB	Output is correct
12	Correct	187 ms	2132 KB	Output is correct

Subtask #2

0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	560 KB	Output is correct
4	Correct	3 ms	1200 KB	Output is correct
5	Correct	5 ms	1200 KB	Output is correct
6	Correct	57 ms	1388 KB	Output is correct
7	Correct	10 ms	1388 KB	Output is correct
8	Correct	42 ms	1664 KB	Output is correct
9	Correct	3 ms	1664 KB	Output is correct
10	Correct	107 ms	1796 KB	Output is correct
11	Correct	2 ms	1796 KB	Output is correct
12	Correct	187 ms	2132 KB	Output is correct
13	Correct	2 ms	2132 KB	Output is correct
14	Correct	85 ms	9940 KB	Output is correct
15	Execution timed out	2049 ms	33268 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-