제출 #59598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59598		IvanC	캥거루 (CEOI16_kangaroo)	C++17	100 / 100	109 ms	32588 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 2010;
const int MOD = 1e9 + 7;

ll dp[MAXN][MAXN];
int N,cs,cf;

ll solve(int atual,int comp){

	if(comp < 0) return 0;
	if(dp[atual][comp] != -1) return dp[atual][comp];

	int lcomp = (atual > cs);
	int rcomp = (atual > cf);

	if(atual == N){
		return dp[atual][comp] = (comp == 0);
	}

	ll total = 0;
	if(atual == cs){
		total += solve(atual+1,comp);// nova componente
		total += solve(atual+1,comp-1)*comp;// conecta a alguma
	}
	else if(atual == cf){
		total += solve(atual+1,comp);// nova componente
		total += solve(atual+1,comp-1)*comp;// conecta a alguma
	}
	else{
		total += solve(atual + 1,comp + 1); // nova componente
		total += solve(atual+1,comp-1)*(comp)*(lcomp + (comp - 1) + rcomp); // conecta duas
	}

	return dp[atual][comp] = (total % MOD);

}

int main(){

	memset(dp,-1,sizeof(dp));
	cin >> N >> cs >> cf;
	cout << solve(1,0) << endl;

	return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49