Submission #62153

#	Time	Username	Problem	Language	Result	Execution time	Memory
62153		bazsi700	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	1840 ms	73884 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL

ll dp[205][205][205][2];
bool was[205][205][205][2];

ll solve(int n, int s, int f, int w) {
	if(s == f) {
		return (n == 1 ? 1 : 0);
	}
	if(n == 2 && ((s < f && w == 1) || (s > f && w == 0))) {
		return 1;
	} else if(n == 2) {
		return 0;
	}
	if(was[n][s][f][w]) {
		return dp[n][s][f][w];
	}
	was[n][s][f][w] = true;
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		if(i == s) {
			continue;
		}
		if(w == 1 && i < s) {
			continue;
		}
		if(w == 0 && i > s) {
			continue;
		}
		ans+= solve(n-1,(i < s ? i : i-1),(f < s ? f : f-1),1-w);
	}
	ans = ans%MOD;
//	cout << n << " " << s << " " << f << " " << w << " " << ans <<  endl;
	dp[n][s][f][w] = ans;
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,s,f;
	cin >> n >> s >> f;
	cout << (solve(n,s,f,0)+solve(n,s,f,1))%MOD;
	return 0;
}

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