Submission #501132

#	Time	Username	Problem	Language	Result	Execution time	Memory
501132		codr0	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	2071 ms	62140 KiB

kangaroo

// Code by Parsa Eslami

#include <bits/stdc++.h>	
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';

using namespace std;
const int N=2000+5;
const int MOD=1e9+7;
int C[N][N];
int dp[N][N][2];//st t 
int ps[N][2];//st

	void pre(){
		FOR(i,0,N-1) C[0][i]=1;
		FOR(i,1,N-1) FOR(j,i,N-1) C[i][j]=(C[i][j-1]+C[i-1][j-1])%MOD;
		dp[1][1][0]=1;
		dp[1][1][1]=1;
		FOR(i0,0,1) FOR(st,1,N-1){
			ps[st][i0]=ps[st-1][i0]+dp[st][1][i0];
		}
		FOR(t,2,N-1){
			FOR(st,1,t){
				dp[st][t][0]=ps[st-1][1]%MOD;
				dp[st][t][1]=(ps[t][0]-ps[st-1][0])%MOD;
			}
			FOR(i0,0,1) FOR(st,1,N-1){
				ps[st][i0]=(ps[st-1][i0]+dp[st][t][i0])%MOD;
			}
		}
	}

	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);	
	
	pre();
	int ans=0;
	int n,st,en; cin>>n>>st>>en;
	if(en<st) swap(en,st);
	if(st==1){
		ans=dp[en-1][n-1][(n&1)];
	}else{
		FOR(i,0,st-2) FOR(j,0,en-st-1) FOR(w,0,n-en){
			int t1=st-2-i;
			int t2=en-st-1-j;
			int t3=n-en-w;
			ans+=((((C[i][st-2]*C[j][en-st-1])%MOD)*C[w][n-en]%MOD)*dp[i+1][(i+j+w+2-1)][(i+j+w+2)&1]%MOD)*dp[t1+t2+1][t1+t2+t3+2-1][(t1+t2+t3)&1];
			ans%=MOD;
		}
	}

	ans=((ans%MOD)+MOD)%MOD;
	cout<<ans<<'\n';

	return 0;
    }

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