답안 #356779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
356779	2021-01-23T16:38:11 Z	Sparky_09	Tents (JOI18_tents)	C++17	100 / 100	127 ms	71060 KB

tents

#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll MOD = 1e9+7;
int h, w;
ll dp[3010][3010];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
  cin >> h >> w;
  for(int i = 0; i <= w; i++){
  	dp[0][i] = 1; 
  }	
  for(int i = 0; i <= h; i++){
  	dp[i][0] = 1;
  }	
  //memset(dp, 0, sizeof dp);
  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      dp[i][j] += dp[i-1][j]; 
      dp[i][j] += 4*j*dp[i-1][j-1]; 
      if(j>1) dp[i][j] += j*(j-1)/2*dp[i-1][j-2]; 
      if(i>1) dp[i][j] += j*(i-1)*dp[i-2][j-1];
      dp[i][j] %= MOD;
    }
  }
  cout << dp[h][w]-1 % 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	748 KB	Output is correct
6	Correct	2 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	1772 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	748 KB	Output is correct
6	Correct	2 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	1772 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	404 KB	Output is correct
14	Correct	6 ms	9708 KB	Output is correct
15	Correct	86 ms	55276 KB	Output is correct
16	Correct	6 ms	4076 KB	Output is correct
17	Correct	20 ms	12908 KB	Output is correct
18	Correct	24 ms	17132 KB	Output is correct
19	Correct	99 ms	63016 KB	Output is correct
20	Correct	78 ms	50944 KB	Output is correct
21	Correct	52 ms	33920 KB	Output is correct
22	Correct	52 ms	35564 KB	Output is correct
23	Correct	32 ms	27096 KB	Output is correct
24	Correct	127 ms	71060 KB	Output is correct
25	Correct	99 ms	61440 KB	Output is correct
26	Correct	115 ms	66796 KB	Output is correct
27	Correct	122 ms	69228 KB	Output is correct