답안 #236709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236709	2020-06-03T06:16:13 Z	anayk	Tents (JOI18_tents)	C++14	100 / 100	144 ms	70776 KB

tents

#include <iostream>

#define int long long
#define MOD 1000000007

signed main() {
  int h, w;
  std::cin >> h >> w;

  int dp[h+1][w+1];
  for(int i = 0; i <= h; i++)
    dp[i][0] = 1;
  for(int i = 0; i <= w; i++)
    dp[0][i] = 1;

  for(int i = 1; i <= h; i++) {
    for(int j = 1; j <= w; j++) {
      dp[i][j] = 0;

      int row = (4*dp[i-1][j-1])%MOD;
      if(j-1) row = (row + (j-1)*dp[i-1][j-2])%MOD;
      dp[i][j] = (dp[i][j] + row*i)%MOD;

      dp[i][j] = (dp[i][j] + dp[i][j-1])%MOD;

      if(i-1) dp[i][j] = (dp[i][j] + (i*(i-1)/2)*dp[i-2][j-1])%MOD;
    }
  }

  std::cout << (dp[h][w]+MOD-1)%MOD << std::endl;
  
  return 0;
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	256 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	4 ms	256 KB	Output is correct
10	Correct	5 ms	640 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	6 ms	1024 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 ms	256 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	4 ms	256 KB	Output is correct
10	Correct	5 ms	640 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	6 ms	1024 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	91 ms	44156 KB	Output is correct
16	Correct	10 ms	3072 KB	Output is correct
17	Correct	25 ms	10112 KB	Output is correct
18	Correct	29 ms	12408 KB	Output is correct
19	Correct	105 ms	51472 KB	Output is correct
20	Correct	85 ms	41208 KB	Output is correct
21	Correct	59 ms	27128 KB	Output is correct
22	Correct	60 ms	26744 KB	Output is correct
23	Correct	33 ms	14976 KB	Output is correct
24	Correct	144 ms	70776 KB	Output is correct
25	Correct	110 ms	52600 KB	Output is correct
26	Correct	126 ms	60280 KB	Output is correct
27	Correct	144 ms	68088 KB	Output is correct