Submission #1162638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162638		Hamed_Ghaffari	Tents (JOI18_tents)	C++20	100 / 100	62 ms	70984 KiB

tents

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

using ll = long long;

const int MXN = 3003;
const ll  MOD = 1e9+7;

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

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> H >> W;
    for(int w=1; w<=W; w++)
        dp[0][w] = 1,
        dp[1][w] = (1 + 4*w + w*(w-1)/2)%MOD;
    for(int h=1; h<=H; h++)
        dp[h][0] = 1,
        dp[h][1] = (1 + 4*h + h*(h-1)/2)%MOD;
    for(int h=2; h<=H; h++)
    for(int w=2; w<=W; w++)
        dp[h][w] = (dp[h-1][w] + w*4*dp[h-1][w-1] + w*(h-1)*dp[h-2][w-1] + w*(w-1)/2*dp[h-1][w-2])%MOD;
    cout << dp[H][W]-1 << '\n';
}

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