제출 #1266864

#제출 시각아이디문제언어결과실행 시간메모리
1266864tanish1e9캥거루 (CEOI16_kangaroo)C++20
6 / 100
0 ms324 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, cs, cf;
	cin >> n >> cs >> cf;
	vector<vector<int>> dp(n+1, vector<int>(n+1, 0));

	dp[1][1] = 1;
	for(int i=2;i<=n;i++) {
		for(int j=i;j>=1;j--) {
			if(i==cs || i==cf) {
				// first ya last component k begin/end me respectively ghus jao
				dp[i][j] += dp[i-1][j];
				// ya fir first ya last me apna hi component bana lo
				dp[i][j] += dp[i-1][j-1];
			}
			else {
				// kinhi do component ke bich me ghuske unko merge kr do
				dp[i][j-1] += dp[i-1][j] * (j-1);
				// kinhi do componenet ke bich apna ek naya component bana lo
				// starting ke pehle aur ending ke baad nahi ja skte 
				dp[i][j] += dp[i-1][j-1] * (j - (i>cs) - (i>cf));
			}
		}
	}
	
	cout << dp[n][1] << endl;

	// for(int i=1;i<=n;i++) {
	// 	for(int j=1;j<=n;j++) {
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...