답안 #339705

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
339705	2020-12-26T02:55:35 Z	eyangch	Tents (JOI18_tents)	C++17	100 / 100	134 ms	70784 KB

tents

#include <bits/stdc++.h>

using namespace std;

long long MOD = 1e9+7;

int H, W;
long long dp[3001][3001];

signed main(){
    cin >> H >> W;
    for(int i = 0; i <= W; i++) dp[0][i] = 1; // one way to make nothing
    for(int i = 0; i <= H; i++) dp[i][0] = 1;
    for(int i = 1; i <= H; i++){
        for(int j = 1; j <= W; j++){
            if(i > 0){
                dp[i][j] += dp[i-1][j]; // nothing on row i up to j
            }if(i > 0 && j > 0){
                dp[i][j] += 4 * j * dp[i-1][j-1]; // one "unattached" tent on row i up to j
            }if(i > 0 && j > 1){
                dp[i][j] += j * (j-1) / 2 * dp[i-1][j-2]; // two attached tents facing each other on row i up to j
            }if(i > 1 && j > 0){
                dp[i][j] += j * (i-1) * dp[i-2][j-1]; // one tent on row i attached to another from prev (0...i-1)
            }
            dp[i][j] %= MOD;
        }
    }
    cout << (dp[H][W]-1+MOD) % MOD << endl;
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	1132 KB	Output is correct
5	Correct	1 ms	768 KB	Output is correct
6	Correct	1 ms	1388 KB	Output is correct
7	Correct	1 ms	876 KB	Output is correct
8	Correct	1 ms	1516 KB	Output is correct
9	Correct	1 ms	876 KB	Output is correct
10	Correct	2 ms	1916 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	2 ms	2284 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	1132 KB	Output is correct
5	Correct	1 ms	768 KB	Output is correct
6	Correct	1 ms	1388 KB	Output is correct
7	Correct	1 ms	876 KB	Output is correct
8	Correct	1 ms	1516 KB	Output is correct
9	Correct	1 ms	876 KB	Output is correct
10	Correct	2 ms	1916 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	2 ms	2284 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	5 ms	9708 KB	Output is correct
15	Correct	88 ms	55148 KB	Output is correct
16	Correct	6 ms	4076 KB	Output is correct
17	Correct	23 ms	12908 KB	Output is correct
18	Correct	25 ms	17132 KB	Output is correct
19	Correct	109 ms	63040 KB	Output is correct
20	Correct	91 ms	50924 KB	Output is correct
21	Correct	53 ms	34028 KB	Output is correct
22	Correct	53 ms	35436 KB	Output is correct
23	Correct	34 ms	27116 KB	Output is correct
24	Correct	128 ms	70784 KB	Output is correct
25	Correct	100 ms	61164 KB	Output is correct
26	Correct	116 ms	66540 KB	Output is correct
27	Correct	134 ms	68972 KB	Output is correct