Submission #101639

#	Time	Username	Problem	Language	Result	Execution time	Memory
101639		KCSC	Tents (JOI18_tents)	C++14	100 / 100	289 ms	35832 KiB

tents

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

const int DIM = 3005;
const int MOD = 1000000007;

int dp[DIM][DIM];

int solve(int n, int m) {
    if (n < 0 || m < 0) {
        return 0; }
    if (n == 0 || m == 0) {
        return 1; }
    if (dp[n][m] != -1) {
        return dp[n][m]; }
    long long ans = 0;
    ans += solve(n - 1, m);
    ans += 4LL * solve(n - 1, m - 1) * m;
    ans += 1LL * solve(n - 1, m - 2) * m * (m - 1) / 2;
    ans += 1LL * solve(n - 2, m - 1) * m * (n - 1);
    return dp[n][m] = ans % MOD; }

int main(void) {
  //  freopen("tents.in", "r", stdin);
  //  freopen("tents.out", "w", stdout);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = -1; } }
    cout << (solve(n, m) - 1 + MOD) % MOD;
    return 0; }

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