Submission #240526

#	Time	Username	Problem	Language	Result	Execution time	Memory
240526		nickmet2004	Tents (JOI18_tents)	C++11	100 / 100	392 ms	71276 KiB

tents

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int mod = 1e9 + 7;

ll dp[3005][3005];

ll DP(int i , int j){
    if(i < 0 || j < 0) return 0;
    if(i == 0 || j == 0) return 1;
    ll &ret = dp[i][j];
    if(ret != -1) return ret;
    ret = 0;
    ret += 4 * j * DP(i - 1 , j - 1) % mod;
    ret %= mod;
    ret += DP(i - 1 , j) % mod;
    ret %= mod;
    ret += (j * (j - 1))/2 * DP(i - 1 , j - 2) % mod;
    ret %= mod;
    ret += j * (i - 1) * DP(i - 2 , j - 1) % mod;
    ret %= mod;
    return ret;
}

int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int h , w;
    cin >> h >> w;
    memset(dp , -1 , sizeof(dp));
    cout << (DP(h , w) + mod - 1) % mod;
return 0;
}

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