Submission #583187

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583187	2022-06-25T03:07:23 Z	Jomnoi	Tents (JOI18_tents)	C++17	100 / 100	80 ms	70880 KB

tents

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

const int MAX_N = 3005;
const int MOD = 1e9 + 7;

long long dp[MAX_N][MAX_N];

int main() {
   cin.tie(nullptr)->sync_with_stdio(false);

   int H, W;
   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;
   }
   for(int i = 1; i <= H; i++) {
      for(int j = 1; j <= W; j++) {
         dp[i][j] += dp[i - 1][j];
         dp[i][j] += dp[i - 1][j - 1] * j * 4;
         if(i >= 2) {
            dp[i][j] += dp[i - 2][j - 1] * j * (i - 1);
         }
         if(j >= 2) {
            dp[i][j] += dp[i - 1][j - 2] * j * (j - 1) / 2;
         }

         dp[i][j] %= MOD;
      }
   }

   dp[H][W]--;
   dp[H][W] += MOD;
   dp[H][W] %= MOD;
   cout << dp[H][W];
   return 0;
}

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	332 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	1108 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	796 KB	Output is correct
8	Correct	2 ms	1348 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	1748 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	2 ms	2116 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	332 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	1108 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	796 KB	Output is correct
8	Correct	2 ms	1348 KB	Output is correct
9	Correct	1 ms	724 KB	Output is correct
10	Correct	2 ms	1748 KB	Output is correct
11	Correct	1 ms	328 KB	Output is correct
12	Correct	2 ms	2116 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	4 ms	9684 KB	Output is correct
15	Correct	55 ms	55192 KB	Output is correct
16	Correct	5 ms	4052 KB	Output is correct
17	Correct	13 ms	12868 KB	Output is correct
18	Correct	16 ms	17108 KB	Output is correct
19	Correct	60 ms	62996 KB	Output is correct
20	Correct	49 ms	50884 KB	Output is correct
21	Correct	33 ms	33772 KB	Output is correct
22	Correct	34 ms	35404 KB	Output is correct
23	Correct	24 ms	27016 KB	Output is correct
24	Correct	72 ms	70880 KB	Output is correct
25	Correct	62 ms	61212 KB	Output is correct
26	Correct	80 ms	66600 KB	Output is correct
27	Correct	72 ms	68972 KB	Output is correct