Submission #817127

#	Time	Username	Problem	Language	Result	Execution time	Memory
817127		gun_gan	Tents (JOI18_tents)	C++17	100 / 100	169 ms	70832 KiB

tents

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

const int MX = 3005, mod = 1e9 + 7, inv = 5e8 + 4;

int H, W;
ll dp[MX][MX];

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> H >> W;

      dp[0][W] = 1;

      for(int i = 0; i < H; i++) {
            for(int a = 0; a <= W; a++) { 
                  dp[i + 1][a] += dp[i][a];
                  dp[i + 1][a] %= mod;

                  if(a - 1 >= 0) {
                        dp[i + 1][a - 1] += 1LL * dp[i][a] * a * 4 % mod;
                        dp[i + 1][a - 1] %= mod;
                  }

                  if(a - 2 >= 0) {
                        dp[i + 1][a - 2] += 1LL * dp[i][a] * a % mod * (a - 1) % mod * inv % mod;
                        dp[i + 1][a - 2] %= mod;
                  }

                  if(i + 2 <= H && a - 1 >= 0) {
                        dp[i + 2][a - 1] += 1LL * dp[i][a] * (H - i - 1) % mod * a % mod;
                        dp[i + 2][a - 1] %= mod;
                  }
            }
      }


      ll ans = 0;
      for(int a = 0; a < W; a++) {
            ans += dp[H][a];
            ans %= mod;
      }

      cout << ans << '\n';
      
}

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