Submission #95038

#	Time	Username	Problem	Language	Result	Execution time	Memory
95038		pranjalssh	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	2 ms	376 KiB

kangaroo

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

#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const int inf = 1e9 + 7;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int dp[2][51][51];
int cdp[2][51][51];
int f(int, int, int, int);
int g(int t, int n, int l, int r) {
	if (l <= 0) return 0;
	int &ans = cdp[t][n][l];
	if (~ans) return ans;
	ans = f(t, n, l, r) + g(t, n, l-1, r);
	if (ans >= inf) ans -= inf;
	return ans;
}
int f(int t, int n, int l, int r) {
	if (l > r) l=n-l+1,r=n-r+1, t^=1;
	if (l == r) return 0;
	if (n == 2) return t == 1;
	int &ans = dp[t][n][l];
	if (~ans) return ans;
	ans = 0;
	if (t == 0) {
		ans = g(1, n-1, l-1, r-1);
		// FOR (i, 1, l - 1) {
		// 	ans += f(1, n-1, i, r-1);
		// 	if (ans >= inf) ans -= inf;
		// }
	} else {
		ans = g(0, n-1, n-1, r-1) - g(0, n-1, l-1, r-1);
		if (ans < 0) ans += inf;
		// FOR (i, l+1, n) {
		// 	ans += f(0, n-1, i-1, r-1);
		// 	if (ans >= inf) ans -= inf;
		// }
	}
	return ans;
}

int F(int n, int l, int r) {
	return (f(0,n,l,r) + f(1,n,l,r))%inf;
}

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

	memset(dp, -1, sizeof dp);
	memset(cdp, -1, sizeof cdp);
	
	int n, l, r; cin >> n >> l >> r;
	cout << F(n,l,r) << "\n";

	return 0;
}

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