Submission #790008

#	Time	Username	Problem	Language	Result	Execution time	Memory
790008		tch1cherin	Tents (JOI18_tents)	C++17	100 / 100	106 ms	35520 KiB

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