Submission #790008

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790008	2023-07-22T09:07:05 Z	tch1cherin	Tents (JOI18_tents)	C++17	100 / 100	106 ms	35520 KB

tents

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

void add(int& a, int b) {
  a += b, a -= a >= MOD ? MOD : 0;
}

int main() {
  int H, W;
  cin >> H >> W;
  int dp[H + 1][W + 1] = {};
  for (int N = 0; N <= H; N++) {
    for (int M = 0; M <= W; M++) {
      if (N == 0 || M == 0) {
        dp[N][M] = 1;
        continue;
      }
      add(dp[N][M], dp[N - 1][M]);
      if (N > 0 && M > 0) {
        add(dp[N][M], 4ll * dp[N - 1][M - 1] * M % MOD);
        if (N > 1) {
          add(dp[N][M], 1ll * dp[N - 2][M - 1] * (N - 1) % MOD * M % MOD); 
        }
        if (M > 1) {
          add(dp[N][M], 1ll * dp[N - 1][M - 2] * (1ll * M * (M - 1) / 2 % MOD) % MOD);
        }
      }
    }
  }
  add(dp[H][W], MOD - 1);
  cout << dp[H][W] << "\n";
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	300 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	2 ms	596 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	296 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	300 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	2 ms	596 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	66 ms	22100 KB	Output is correct
16	Correct	5 ms	1612 KB	Output is correct
17	Correct	15 ms	5184 KB	Output is correct
18	Correct	18 ms	6312 KB	Output is correct
19	Correct	77 ms	25812 KB	Output is correct
20	Correct	61 ms	20564 KB	Output is correct
21	Correct	43 ms	13716 KB	Output is correct
22	Correct	40 ms	13524 KB	Output is correct
23	Correct	22 ms	7508 KB	Output is correct
24	Correct	106 ms	35520 KB	Output is correct
25	Correct	78 ms	26324 KB	Output is correct
26	Correct	91 ms	30244 KB	Output is correct
27	Correct	101 ms	34144 KB	Output is correct