답안 #962385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962385	2024-04-13T12:04:54 Z	abczz	Tents (JOI18_tents)	C++14	100 / 100	127 ms	70692 KB

tents

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const ll M = 1e9 + 7;
ll h, w, f, dp[3001][3001];
int main() {
  cin >> h >> w;
  for (int i=0; i<=h; ++i) dp[i][0] = 1;
  for (ll i=1; i<=h; ++i) {
    for (ll j=1; j<=w; ++j) {
      if (i != 1) dp[i][j] = dp[i-1][j];
      dp[i][j] += dp[i-1][j-1] * (w-j+1) % M * 4 % M;
      dp[i][j] %= M;
      if (j >= 2) dp[i][j] += dp[i-1][j-2] * ((w-j+2) * (w-j+1) / 2 % M) % M;
      dp[i][j] %= M;
      if (i >= 2) dp[i][j] += dp[i-2][j-1] * (i-1) % M * (w-j+1) % M;
      dp[i][j] %= M;
    }
  }
  for (int j=1; j<=w; ++j) {
    f += dp[h][j];
    f %= M;
  }
  cout << f << '\n';
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	2 ms	8540 KB	Output is correct
11	Correct	1 ms	2392 KB	Output is correct
12	Correct	3 ms	8540 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	2392 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	2 ms	8540 KB	Output is correct
11	Correct	1 ms	2392 KB	Output is correct
12	Correct	3 ms	8540 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	22 ms	55604 KB	Output is correct
15	Correct	82 ms	66140 KB	Output is correct
16	Correct	8 ms	6584 KB	Output is correct
17	Correct	18 ms	16984 KB	Output is correct
18	Correct	28 ms	29016 KB	Output is correct
19	Correct	93 ms	70236 KB	Output is correct
20	Correct	73 ms	57948 KB	Output is correct
21	Correct	48 ms	39512 KB	Output is correct
22	Correct	49 ms	51804 KB	Output is correct
23	Correct	32 ms	70356 KB	Output is correct
24	Correct	122 ms	70692 KB	Output is correct
25	Correct	91 ms	62140 KB	Output is correct
26	Correct	119 ms	68188 KB	Output is correct
27	Correct	127 ms	70356 KB	Output is correct