Submission #1255949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255949		mngoc._.	Tents (JOI18_tents)	C++20	100 / 100	211 ms	96656 KiB

tents

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define endl "\n"
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
const int MAXN = 1e6 + 5;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int MAX_SUM = 100000;

int dp[3501][3501];
int f(int r , int c){
    if(r <= 0 ||  c <= 0) return 1;
    if(dp[r][c] != -1) return dp[r][c];
    dp[r][c] = ((f(r - 1 , c -2 ) % MOD * (c * (c - 1))/2)%MOD + (f(r -2 , c - 1) * (r - 1) * c)%MOD + 
    f(r - 1 , c)%MOD + (f(r - 1 , c - 1) * c * 4)%MOD)%MOD;
    return dp[r][c];
     

}
signed main(){
    faster;
    // freopen("TASK.INP", "r", stdin);
    // freopen("TASK.OUT", "w", stdout);
    int r , c;
    cin >> r >> c;
    memset(dp , -1 , sizeof(dp));
    cout << f(r , c) - 1;
    





    cerr << "Time elapsed: " << TIME << " s.\n";
    return 0;
}

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