제출 #605324

#제출 시각아이디문제언어결과실행 시간메모리
605324gromperenKangaroo (CEOI16_kangaroo)C++14
51 / 100
931 ms273796 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long


const int MAXN = 205;
const int MOD = 1e9+7;
//vector<vector<vector<vector<ll>>>>dp(MAXN, vector<vector<vector<ll>>>(MAXN, vector<vector<ll>>(MAXN, vector<ll>(2, -1))));
ll dp[MAXN][MAXN][MAXN][2];

ll f(int n, int s, int t, int dir) {
	if (dp[n][s][t][dir] != -1) return dp[n][s][t][dir];
	if (s == t) return dp[n][s][t][dir] = 0;
	ll ans = 0;
	int tt = t-(s<t);
	if (dir) {
		for (int i = 1; i < s; ++i) {
			ans += f(n-1,i,tt,0);
			ans %= MOD;
		}
	} else {
		for (int i = s+1; i <= n; ++i) {
			ans += f(n-1, i-1, tt, 1);
			ans %= MOD;
		}
	}
	return dp[n][s][t][dir] = ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, cs, cf; cin >> n >> cs >> cf;
	memset(dp, -1, sizeof(dp));
	dp[1][1][1][0] = 1; 
	dp[1][1][1][1] = 1; 

	cout << (f(n,cs,cf,0) + f(n,cs,cf,1)) % MOD<<"\n";




	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...