답안 #956865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956865 2024-04-02T15:08:26 Z LCJLY Tents (JOI18_tents) C++14
100 / 100
186 ms 71308 KB
#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();
	}
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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