Submission #583187

#	Time	Username	Problem	Language	Result	Execution time	Memory
583187		Jomnoi	Tents (JOI18_tents)	C++17	100 / 100	80 ms	70880 KiB

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 / 48
• Subtask 2: 52 / 52