제출 #236926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236926		aryan12	Tents (JOI18_tents)	C++17	100 / 100	475 ms	71416 KiB

tents

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long N = 3010;
long long dp[N][N];

long long Recur(long long row, long long col) {
    if(row < 0 || col < 0)
        return 0;
    if(row == 0 || col == 0)
        return 1;
    if(dp[row][col] != -1)
        return dp[row][col];
    long long ans = 0, temp = 0;

    //the row is empty
    temp = Recur(row, col - 1);
    ans = temp;

    //1 tent facing anywhere
    temp = ((Recur(row - 1, col - 1) * row) % MOD * 4) % MOD;
    ans = (ans + temp) % MOD;

    //2 tents facing each other (row-wise)
    temp = (Recur(row - 2, col - 1) * (((row * (row - 1)) / 2) % MOD)) % MOD;
    ans = (ans + temp) % MOD;

    //2 tents facing each other (column-wise)
    temp = (Recur(row - 1, col - 2));
    long long x = row * (col - 1) % MOD;
    temp *= x;
    temp %= MOD;
    ans = (ans + temp) % MOD;
    dp[row][col] = ans;
    return ans;
}

void Solve() {
    long long n, m;
    cin >> n >> m;
    for(long long i = 0; i <= n; i++) {
        for(long long j = 0; j <= m; j++) {
            dp[i][j] = -1;
        }
    }
    long long ans = Recur(n, m) - 1;
    if(ans < 0)
        ans += MOD;
    cout << ans << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Solve();
    return 0;
}

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