Submission #1222086

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

kangaroo

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

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