Submission #962385

#	Time	Username	Problem	Language	Result	Execution time	Memory
962385		abczz	Tents (JOI18_tents)	C++14	100 / 100	127 ms	70692 KiB

tents

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const ll M = 1e9 + 7;
ll h, w, f, dp[3001][3001];
int main() {
  cin >> h >> w;
  for (int i=0; i<=h; ++i) dp[i][0] = 1;
  for (ll i=1; i<=h; ++i) {
    for (ll j=1; j<=w; ++j) {
      if (i != 1) dp[i][j] = dp[i-1][j];
      dp[i][j] += dp[i-1][j-1] * (w-j+1) % M * 4 % M;
      dp[i][j] %= M;
      if (j >= 2) dp[i][j] += dp[i-1][j-2] * ((w-j+2) * (w-j+1) / 2 % M) % M;
      dp[i][j] %= M;
      if (i >= 2) dp[i][j] += dp[i-2][j-1] * (i-1) % M * (w-j+1) % M;
      dp[i][j] %= M;
    }
  }
  for (int j=1; j<=w; ++j) {
    f += dp[h][j];
    f %= M;
  }
  cout << f << '\n';
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52