Submission #236709

#	Time	Username	Problem	Language	Result	Execution time	Memory
236709		anayk	Tents (JOI18_tents)	C++14	100 / 100	144 ms	70776 KiB

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