Submission #410247

#	Time	Username	Problem	Language	Result	Execution time	Memory
410247		Blagojce	Kangaroo (CEOI16_kangaroo)	C++11	51 / 100	951 ms	523596 KiB

kangaroo

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define all(v) begin(v), end(v)
#define pq priority_queue
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const ll inf = 1e18;
const ll mod = 1e9+7;
const int mxn = 2e5;


int n, f, s;
int p = 0;

ll dp[202][202][202][2][2];

ll g(int a, int b, int pos, int side){
	
	if(dp[a][b][pos][side][p] != -1) return dp[a][b][pos][side][p];
	
	int dir = ((a+b)&1)^p;
	ll ret = 0;
	if(side == 0){
		if(dir == 0){
			if(b == 0 && a == 1){
				return 0;
			}
			
			fr(ipos, 0, pos){
				ret += g(a-1, b, ipos, 0);
				ret %= mod;
			}
		}
		else{
			if(b == 0 && a == 1){
				return 1;
			}
			
			fr(ipos, pos, a-1){
				ret += g(a-1, b, ipos, 0);
				ret %= mod;
			}
			fr(ipos, 0, b){
				ret += g(a-1, b, ipos, 1);
				ret %= mod;
			}
		}
	}
	else{
		if(dir == 1){
			if(a == 0 && b == 1){
				return 0;
			}
			
			fr(ipos, pos, b-1){
				ret += g(a, b-1, ipos, 1);
				ret %= mod;
			}
		}
		else{
			if(a == 0 && b == 1){
				return 1;
			}
			
			fr(ipos, 0, pos){
				ret += g(a, b-1, ipos, 1);
				ret %= mod;
			}
			fr(ipos, 0, a){
				ret += g(a, b-1, ipos, 0);
				ret %= mod;
			}
		}
	}
	dp[a][b][pos][side][p] = ret;
	return ret;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> s >> f;
	
	if(s > f) swap(s, f);
	--s, --f;
	memset(dp, -1, sizeof(dp));
	
	int A = f;
	int B = n-A-1;
	ll tot = g(A, B, s, 0);
	p = 1;
	tot += g(A, B, s, 0);
	tot %= mod;
	cout<<tot<<endl;
}

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