Submission #1079667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079667		DeathIsAwe	Tents (JOI18_tents)	C++17	100 / 100	115 ms	70936 KiB

tents

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1000000007;
ll dp[3001][3001];


int main() {
    int h,w; cin >> h >> w;
    for (int i=0;i<3001;i++) {
        for (int j=0;j<3001;j++) {
            dp[i][j] = 0;
        }
    }
    for (int i=0;i<3001;i++) {
        dp[i][0] = 1; dp[0][i] = 1;
    }


    for (int i=1;i<h+1;i++) {
        for (int j=1;j<w+1;j++) {
            dp[i][j] += dp[i-1][j];
            dp[i][j] += (4 * j) * dp[i-1][j-1]; dp[i][j] %= mod;
            if (i > 1) {
                dp[i][j] += (i - 1)  * j * dp[i-2][j-1]; dp[i][j] %= mod;
            }
            if (j > 1) {
                dp[i][j] += j * (j - 1) * dp[i-1][j-2] / 2; dp[i][j] %= mod;
            }
            //cout << dp[i][j] << ' ';
        }
        //cout << '\n';
    }
    cout << dp[h][w] - 1;
}

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