제출 #1284024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284024		hungdt	Tents (JOI18_tents)	C++20	100 / 100	69 ms	70964 KiB

tents

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3005;
const long long mod = 1e9 + 7;
long long dp[maxn][maxn];
int m, n;

int main()
{
    cin >> m >> n;

    for (int i=0; i<=m; i++) dp[i][0] = 1;

    for (int i=1; i<=m; i++){
        for (int j=1; j<=n; j++){
            int re = n - j;
            dp[i][j] = dp[i - 1][j]; // no tents are put
            dp[i][j] += dp[i - 1][j - 1] * 4 * (re + 1); // put one tent and choose its direction
            dp[i][j] %= mod;
            if (i >= 2) dp[i][j] += dp[i - 2][j - 1] * (re + 1) * (i - 1); // one tent and the column already has one
            dp[i][j] %= mod;
            if (j >= 2) dp[i][j] += dp[i - 1][j - 2] * (re + 2) * (re + 1) / 2; // two tents
            dp[i][j] %= mod;
        }
    }

    long long ans = 0;
    for (int i=1; i<=n; i++){
        ans += dp[m][i];
        ans %= mod;
    }

    cout << ans;

    return 0;
}

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