Submission #240526

#TimeUsernameProblemLanguageResultExecution timeMemory
240526nickmet2004Tents (JOI18_tents)C++11
100 / 100
392 ms71276 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...