Submission #1162638

#TimeUsernameProblemLanguageResultExecution timeMemory
1162638Hamed_GhaffariTents (JOI18_tents)C++20
100 / 100
62 ms70984 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...