Submission #59598

#TimeUsernameProblemLanguageResultExecution timeMemory
59598IvanCKangaroo (CEOI16_kangaroo)C++17
100 / 100
109 ms32588 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...