Submission #163298

#	Time	Username	Problem	Language	Result	Execution time	Memory
163298		ryansee	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	2056 ms	137392 KiB

kangaroo

#include "bits/stdc++.h"
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }
 
#define ll /*long long*/ int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;
 
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (206)
ll mem[MAXN][MAXN][MAXN][2][2], n, cs, cf, mod=1e9+7;
ll dp(ll a, ll b, ll c, ll flag, ll lr) { // flag -> 0 means only can jump left, lr -> 0 means left of cf
	if(a<0||b<0||c<0) return 0;
	if(~mem[a][b][c][flag][lr]) return mem[a][b][c][flag][lr];
	if(a == 0 && b == 0 && c == 0) return lr != flag;
	ll x = 0;
	if(lr) { // node right of cf
		if(flag == 0) {
			FOR(i,0,b-1) {
				x += dp(a,i,c+b-i-1,1,1), x%=mod;
			}
			FOR(i,0,a-1) {
				x += dp(i, a-i-1, b+c, 1, 0), x%=mod;
			}
		} else {
			FOR(i,0,c-1) {
				x += dp(a, b+i, c-i-1, 0, 1), x%=mod;
			}
		}
	} else { // node left of cf
		if(flag == 1) {
			FOR(i,0,b-1) {
				x += dp(a+i, b-i-1, c, 0, 0), x%=mod;
			}
			FOR(i,0,c-1) {
				x += dp(a+b, i, c-i-1, 0, 1), x%=mod;
			}
		} else {
			FOR(i,0,a-1) {
				x += dp(i, a-i-1+b, c, 1, 0), x%=mod; 
			}
		}
	}
	return mem[a][b][c][flag][lr]=x;
}
int main()
{
	// freopen("kangaroo.in","r",stdin);
	// freopen("kangaroo.out","w",stdout);
	cin>>n>>cs>>cf; mmst(mem,-1);
	if(cs < cf) {
		cout<<(dp(cs-1, cf-cs-1, n-cf, 0, 0) + dp(cs-1, cf-cs-1, n-cf, 1, 0))%mod<<'\n';
	} else {
		cout<<(dp(cf-1, cs-cf-1, n-cs, 0, 1) + dp(cf-1, cs-cf-1, n-cs, 1, 1))%mod<<'\n';
	}
}

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