제출 #605313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
605313		gromperen	캥거루 (CEOI16_kangaroo)	C++14	6 / 100	555 ms	475968 KiB

kangaroo

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

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