Submission #1313012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313012		boclobanchat	캥거루 (CEOI16_kangaroo)	C++20	100 / 100	24 ms	25576 KiB

kangaroo

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

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