Submission #605273

#	Time	Username	Problem	Language	Result	Execution time	Memory
605273		sofapuden	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	910 ms	273868 KiB

kangaroo

#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';
}

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