제출 #605273

#제출 시각아이디문제언어결과실행 시간메모리
605273sofapuden캥거루 (CEOI16_kangaroo)C++14
51 / 100
910 ms273868 KiB
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int mxN = 2e2+5;
const int MOD = 1e9+7;
 
ll dp[mxN][mxN][mxN][2];
 
ll f(int ind, int l, int r, int dir){
	if(dp[ind][l][r][dir] != -1)return dp[ind][l][r][dir];
	if(l == r)return 0;
	ll ret = 0;
	int nr = r - (l < r);
	if(dir){
		for(int i = l; i < ind; ++i){
			ret+=f(ind-1,i,nr,dir^1);
			ret%=MOD;
		}
		return dp[ind][l][r][dir] = ret;
	} else {
		for(int i = l-1; i; --i){
			ret+=f(ind-1,i,nr,dir^1);
			ret%=MOD;
		}
		return dp[ind][l][r][dir] = ret;
	}
}
 
int main(){
	int n, cs, cf; cin >> n >> cs >> cf;
	for(int i = 0; i < mxN; ++i)for(int j = 0; j < mxN; ++j)for(int k = 0; k < mxN; ++k)dp[i][j][k][0] = dp[i][j][k][1] = -1;
	dp[1][1][1][0] = dp[1][1][1][1] = 1;
	cout << (f(n,cs,cf,0) + f(n,cs,cf,1))%MOD << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...