제출 #1227956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227956		takoshanava	Tents (JOI18_tents)	C++20	100 / 100	203 ms	71324 KiB

tents

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 3005, MOD = 1e9 + 7;
int dp[N][N];

int go(int x, int y){
    if(x <= 0 or y <= 0) return 1;
    if(dp[x][y] != -1) return dp[x][y];
    dp[x][y] = 0;
    dp[x][y] = (dp[x][y] + go(x - 1, y) + MOD) % MOD;
    dp[x][y] = (dp[x][y] + go(x - 1, y - 2) * y * (y - 1) / 2 + MOD) % MOD;
    dp[x][y] = (dp[x][y] + go(x - 1, y - 1) * 4 * y + MOD) % MOD;
    dp[x][y] = (dp[x][y] + go(x - 2, y - 1) * y * (x - 1) + MOD) % MOD; 
    return dp[x][y];
}

signed main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0 ; i < N; i++){
        for(int j = 0; j < N; j++){
            dp[i][j] = -1;
        }
    }
    cout << go(n, m) - 1;
}

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