Submission #956865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
956865	2024-04-02T15:08:26 Z	LCJLY	Tents (JOI18_tents)	C++14	100 / 100	186 ms	71308 KB

tents

#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int mod=1e9+7;
int memo[3005][3005];

int f(int n){
	int hold=n*(n-1)/2;
	hold=(hold+mod)%mod;
	//show2(n,n,hold,hold);
	return hold;
}

int dp(int a, int b){
	if(a==0||b==0) return 1;
	if(a<0||b<0) return 0;
	if(memo[a][b]!=-1) return memo[a][b];
	
	int ans=0;
	
	ans=(ans+dp(a-1,b));
	if(a>=2&&b>=1){
		int hold=dp(a-2,b-1)*(a-1)*b;
		hold%=mod;
		ans=(ans+hold)%mod;
	}
	if(a>=1&&b>=2){
		int hold=dp(a-1,b-2)*f(b);
		hold%=mod;
		ans=(ans+hold)%mod;
	}
	if(a>=1&&b>=1){
		int hold=dp(a-1,b-1)*4*b;
		hold%=mod;
		ans=(ans+hold)%mod;
	}
	return memo[a][b]=ans;
}

void solve(){
	int n,k;
	cin >> n >> k;
	
	memset(memo,-1,sizeof(memo));
	cout << dp(n,k)-1;
	
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//freopen("in.txt","w",stdout);
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	71004 KB	Output is correct
2	Correct	10 ms	71004 KB	Output is correct
3	Correct	10 ms	71004 KB	Output is correct
4	Correct	10 ms	71004 KB	Output is correct
5	Correct	10 ms	71004 KB	Output is correct
6	Correct	10 ms	71004 KB	Output is correct
7	Correct	10 ms	71004 KB	Output is correct
8	Correct	10 ms	71000 KB	Output is correct
9	Correct	9 ms	71004 KB	Output is correct
10	Correct	12 ms	71128 KB	Output is correct
11	Correct	9 ms	71004 KB	Output is correct
12	Correct	12 ms	71004 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	71004 KB	Output is correct
2	Correct	10 ms	71004 KB	Output is correct
3	Correct	10 ms	71004 KB	Output is correct
4	Correct	10 ms	71004 KB	Output is correct
5	Correct	10 ms	71004 KB	Output is correct
6	Correct	10 ms	71004 KB	Output is correct
7	Correct	10 ms	71004 KB	Output is correct
8	Correct	10 ms	71000 KB	Output is correct
9	Correct	9 ms	71004 KB	Output is correct
10	Correct	12 ms	71128 KB	Output is correct
11	Correct	9 ms	71004 KB	Output is correct
12	Correct	12 ms	71004 KB	Output is correct
13	Correct	10 ms	71004 KB	Output is correct
14	Correct	10 ms	71104 KB	Output is correct
15	Correct	117 ms	71300 KB	Output is correct
16	Correct	14 ms	71000 KB	Output is correct
17	Correct	21 ms	71004 KB	Output is correct
18	Correct	35 ms	71004 KB	Output is correct
19	Correct	134 ms	71308 KB	Output is correct
20	Correct	111 ms	71256 KB	Output is correct
21	Correct	65 ms	71004 KB	Output is correct
22	Correct	72 ms	71260 KB	Output is correct
23	Correct	53 ms	71260 KB	Output is correct
24	Correct	186 ms	71256 KB	Output is correct
25	Correct	128 ms	71276 KB	Output is correct
26	Correct	148 ms	71256 KB	Output is correct
27	Correct	168 ms	71256 KB	Output is correct