Submission #229685

#	Time	Username	Problem	Language	Result	Execution time	Memory
229685		DS007	Tents (JOI18_tents)	C++14	100 / 100	476 ms	70904 KiB

tents

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

const int mod = 1e9 + 7;

int solveTestCase(int test) {
    int h, w;
    cin >> h >> w;

    int dp[h + 1][w + 1] = {};
    dp[1][1] = 4;

    for (int i = 2; i <= h; i++) {
        dp[i][1] = i * 4 + i * (i - 1) / 2;
        dp[i][1] %= mod;
    }

    for (int i = 2; i <= w; i++) {
        dp[1][i] = i * 4 + i * (i - 1) / 2;
        dp[1][i] %= mod;
    }

    for (int i = 2; i <= h; i++) {
        for (int j = 2; j <= w; j++) {
            dp[i][j] += (i + j - 1) * 4 * (dp[i - 1][j - 1] + 1) % mod - (i - 1) * (j - 1) * 16 * (dp[i - 2][j - 2] + 1) % mod + mod;
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (i - 2) / 2 * (j - 1) * (j - 2) / 2 % mod * ((i >= 3) * (j >= 3) * dp[i - 3][j - 3] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (dp[i - 2][j - 1] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (j - 1) * (dp[i - 1][j - 2] + 1);
            dp[i][j] %= mod;
            dp[i][j] += dp[i - 1][j - 1];
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (j - 1) * 2 * (dp[i - 2][j - 2] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (j - 1) * (j - 2) * (i - 2) % mod * ((i >= 3) * (j >= 3) * dp[i - 3][j - 3] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (i - 2) / 2 * (dp[i - 3][j - 1] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (j - 1) * (j - 2) / 2 * (dp[i - 1][j - 3] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (i - 2) / 2 * (j - 1) * (i - 3) % mod * (dp[i - 4][j - 2] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (j - 1) * (j - 2) / 2 * (i - 1) * (j - 3) % mod * (dp[i - 2][j - 4] + 1);
            dp[i][j] %= mod;
        }
    }

    cout << dp[h][w];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase(i);
}

Compilation message (stderr)

tents.cpp: In function 'long long int solveTestCase(long long int)':
tents.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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