답안 #305618

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
305618 2020-09-23T17:24:11 Z youngyojun Tents (JOI18_tents) C++17
100 / 100
305 ms 106232 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MOD = 1000000007;
const int MAXH = 3005;
const int MAXW = 3005;
 
int dp[MAXW][MAXH], ds[MAXW][MAXH], dks[MAXW][MAXH];
 
int H, W;
 
int main() {
	for(int i = 0; i < MAXH; i++) dp[0][i] = dp[i][0] = 1;
	for(int i = 0; i < MAXH; i++) ds[0][i] = i+1;
	dks[0][0] = 1; for(int i = 1; i < MAXH; i++) dks[0][i] = (dks[0][i-1] + i+1) % MOD;
 
	cin >> H >> W;
 
	for(int w = 1; w <= W; w++) {
		for(int h = 1; h <= H; h++) {
			int &ret = dp[w][h];
			ret = (ll(ds[w-1][h-1]) * w % MOD * 4 + ret) % MOD;
			if(1 < h) ret = (ll(dks[w-1][h-2]) * w + ret) % MOD;
			if(1 < w) ret = (ll(w) * (w-1) / 2 % MOD * ds[w-2][h-1] + ret) % MOD;
			ret = (ret + 1) % MOD;
		}
		ds[w][0] = 1; for(int j = 1; j <= H; j++) ds[w][j] = (ds[w][j-1] + dp[w][j]) % MOD;
		dks[w][0] = 1; for(int j = 1; j <= H; j++) dks[w][j] = (ll(dp[w][j]) * (j+1) + dks[w][j-1]) % MOD;
	}
 
	cout << ((dp[W][H] - 1 + MOD) % MOD) << endl;
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12544 KB Output is correct
2 Correct 8 ms 13952 KB Output is correct
3 Correct 7 ms 12416 KB Output is correct
4 Correct 7 ms 12416 KB Output is correct
5 Correct 8 ms 14592 KB Output is correct
6 Correct 8 ms 13312 KB Output is correct
7 Correct 8 ms 14464 KB Output is correct
8 Correct 8 ms 13056 KB Output is correct
9 Correct 7 ms 12416 KB Output is correct
10 Correct 9 ms 14080 KB Output is correct
11 Correct 10 ms 14848 KB Output is correct
12 Correct 12 ms 15872 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 12544 KB Output is correct
2 Correct 8 ms 13952 KB Output is correct
3 Correct 7 ms 12416 KB Output is correct
4 Correct 7 ms 12416 KB Output is correct
5 Correct 8 ms 14592 KB Output is correct
6 Correct 8 ms 13312 KB Output is correct
7 Correct 8 ms 14464 KB Output is correct
8 Correct 8 ms 13056 KB Output is correct
9 Correct 7 ms 12416 KB Output is correct
10 Correct 9 ms 14080 KB Output is correct
11 Correct 10 ms 14848 KB Output is correct
12 Correct 12 ms 15872 KB Output is correct
13 Correct 15 ms 27264 KB Output is correct
14 Correct 7 ms 12544 KB Output is correct
15 Correct 194 ms 75664 KB Output is correct
16 Correct 27 ms 29176 KB Output is correct
17 Correct 59 ms 41504 KB Output is correct
18 Correct 66 ms 41336 KB Output is correct
19 Correct 223 ms 82428 KB Output is correct
20 Correct 184 ms 78968 KB Output is correct
21 Correct 133 ms 69240 KB Output is correct
22 Correct 127 ms 61432 KB Output is correct
23 Correct 69 ms 31992 KB Output is correct
24 Correct 305 ms 106232 KB Output is correct
25 Correct 230 ms 93036 KB Output is correct
26 Correct 259 ms 97272 KB Output is correct
27 Correct 289 ms 104972 KB Output is correct