oj.uz

Submission #237171

# Submission time Handle Problem Language Result Execution time Memory
237171 2020-06-05T04:59:07 Z Falcon Tents (JOI18_tents) C++14
100 / 100
 437 ms 72312 KB 
#include <bits/stdc++.h>

#define __DEBUG 0
#define all(c) (c).begin(), (c).end()
#define tr(c, it) for(auto it = c.begin(); it != c.end(); it++)
#define setAll(x, k) memset(x, k, sizeof(x))
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, s, e) for(int i = s; i <= e; i++)
#define rep3(i, s, e, d) for(int i = s; d >= 0 ? i <= e : i >= e; i += d)
#define pb push_back
#define DBG2(x) if(__DEBUG) cerr << "<" << __LINE__ << "> " << #x << ": " << x << endl
#define DBG if(__DEBUG) cerr
#define pii pair<int, int>

#define int ll

using namespace std;

typedef long long ll;

const int mod = 1000000007;


int dp[3001][3001];
bool ch[3001][3001];

int rec(int H, int W){
	if(H < 0 || W < 0)
		return 0;
	if(W == 0 || H == 0)
		return 1;
	if(ch[H][W])
		return dp[H][W];
	ch[H][W] = 1;
	return dp[H][W] = ((rec(H, W - 1) + H * (H - 1) / 2 * rec(H - 2, W - 1) % mod) % mod 
		+ (H * (W - 1) * rec(H - 1, W - 2) % mod + 4 * H * rec(H - 1, W - 1) % mod) % mod) % mod;

}

signed main(){

	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr), cout.tie(nullptr);

#if __DEBUG
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	freopen("debug", "w", stderr);
#endif

	int H, W;
	cin >> H >> W;
	cout << rec(H, W) - 1 << endl;
 
	
#if __DEBUG
	system(R"(notepad .\out)");
#endif
	return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 1664 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 2432 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 9 ms 2944 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 1664 KB Output is correct
7 Correct 6 ms 1280 KB Output is correct
8 Correct 5 ms 1152 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 2432 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 9 ms 2944 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 266 ms 48524 KB Output is correct
16 Correct 18 ms 4992 KB Output is correct
17 Correct 57 ms 14072 KB Output is correct
18 Correct 72 ms 18040 KB Output is correct
19 Correct 313 ms 55288 KB Output is correct
20 Correct 242 ms 46584 KB Output is correct
21 Correct 162 ms 33528 KB Output is correct
22 Correct 146 ms 32788 KB Output is correct
23 Correct 28 ms 12152 KB Output is correct
24 Correct 435 ms 72312 KB Output is correct
25 Correct 323 ms 57724 KB Output is correct
26 Correct 400 ms 64252 KB Output is correct
27 Correct 437 ms 70392 KB Output is correct