Submission #1222156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222156		boclobanchat	Kangaroo (CEOI16_kangaroo)	C++20	51 / 100	2096 ms	27404 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2048;
const int mod=1e9+7;
int dp[MAXN][MAXN],pref[MAXN],suff[MAXN],C[MAXN][MAXN];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,s,f;
	cin>>n>>s>>f;
	if(s>f) swap(s,f);
	C[0][0]=1;
	for(int i=1;i<=n;i++) for(int j=0;j<=i;j++)
	{
		C[i][j]=C[i-1][j];
		if(j) C[i][j]=(C[i][j]+C[i-1][j-1])%mod;
	}
	for(int i=1;i<=n;i++) if(i==1) dp[1][1]=1;
	else if(i%2==0) for(int j=1;j<=i;j++) dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%mod;
	else for(int j=i;j;j--) dp[i][j]=(dp[i][j+1]+dp[i-1][j])%mod;
	if(f==n) return cout<<dp[n-1][s],0;
	int ans=0,x=f-s-1,y=n-f-1;
	s--;
	for(int i=0;i<=s;i++) for(int j=0;j<=x;j++) for(int k=0;k<=y;k++) ans=(ans+1LL*C[s][i]*C[x][j]%mod*C[y][k]%mod*dp[i+j+k+1][i+1]%mod*dp[n-2-i-j-k][f-i-j-1]%mod)%mod;
	cout<<ans;
}

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