제출 #49256

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

kangaroo

#include <bits/stdc++.h>
 
 
#define pb push_back
#define nl puts ("")
#define sp printf ( " " )
#define phl printf ( "hello\n" )
#define ff first
#define ss second
#define POPCOUNT __builtin_popcountll
#define RIGHTMOST __builtin_ctzll
#define LEFTMOST(x) (63-__builtin_clzll((x)))
#define MP make_pair
#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
#define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
#define SQ(x) ((x)*(x))
#define ABS(x) ((x)<0?-(x):(x))
#define FABS(x) ((x)+eps<0?-(x):(x))
#define ALL(x) (x).begin(),(x).end()
#define LCM(x,y) (((x)/gcd((x),(y)))*(y))
#define SZ(x) ((vlong)(x).size())
#define NORM(x) if(x>=mod) x-=mod;if(x<0) x+=mod;
#define MOD(x,y) (((x)*(y))%mod)
#define ODD(x) (((x)&1)==0?(0):(1))
#define Set(N,cur) N=(N|(1LL<<cur))
#define Reset(N,cur) N=(N&(~(1LL<<cur)))
#define Check(N,cur) (!((N&(1LL<<cur))==0))
#define fast_cin ios_base::sync_with_stdio(false);cin.tie(NULL)
#define dump(x) cerr<<"~ "<<#x<<" = "<<x<<endl
//Imran addition
#define rep(i,n) for(int i = 1; i <= n; i++)
#define mem CLR
#define pf printf
#define sc scanf
#define endl "\n"
#define gi(k) scanf("%d",&k)
#define gl(k) scanf("%lld",&k)
#define NMAX 2147483647
#define LMAX 9223372036854775807LL
 
using namespace std;
 
 
#define LL long long
#define LLU long long unsigned int
typedef long long vlong;
typedef unsigned long long uvlong;
typedef pair < int, int > pii;
typedef pair < vlong, vlong > pll;
typedef vector<int> vi;
typedef vector<vlong> vl;
typedef vector<pll> vll;
 
inline vlong gcd ( vlong a, vlong b ) {
    a = ABS ( a ); b = ABS ( b );
    while ( b ) { a = a % b; swap ( a, b ); } return a;
}
 
 
const vlong inf = 2147383647;
const vlong mod = 1000000007;
const double pi = 2 * acos ( 0.0 );
const double eps = 1e-9;

vlong dp[202][202][202];
 

vlong f(int lf, int ri, int tri, int flag) {
	vlong &res = dp[lf][ri][tri];

	if(res != -1) return res;

	if(lf + ri == 1) {
		//pf("DD %d %d\n",ri,tri);
		return res = lf ^ flag; //ri ^ flag
	}

	res = 0;
	int dir;

	if((lf+ri) & 1) dir = flag;
	else dir = flag ^ 1; 

	if(!dir) { //going to left

		if(ri < tri) { //current is right of target
			int x = tri - ri;

			for(int i = 1; i < x; i++) {
				res = (res + f(lf-i, ri+i-1, tri-1, flag)) % mod;
			}

			for(int i = x+1; i <= lf; i++) {
				res = (res + f(lf-i, ri+i-1, tri, flag)) % mod;
			}
		}


		else {
			for(int i = 1; i <= lf; i++) {
				res = (res + f(lf-i, ri+i-1, tri, flag)) % mod;
			}
		}

	}

	else {	//going to right

		if(ri < tri) {
			for(int i = 1; i <= ri; i++) {
				res = (res + f(lf+i-1, ri-i, tri-1, flag)) % mod;
			}
		}

		else {
			int x = ri-tri+1;

			for(int i = 1; i < x; i++) {
				res = (res + f(lf+i-1, ri-i, tri, flag)) % mod;
			}

			for(int i = x+1; i <= ri; i++) {
				res = (res + f(lf+i-1, ri-i, tri-1, flag)) % mod;
			}
		}
	}


	return res;
}
 
 
int main () {
 
 	#ifdef forthright48
    freopen ( "00_input.txt", "r", stdin ); //freopen ( "00_output.txt", "w", stdout );
 	#endif

 	int n,a,b,x,y,z;
 	vlong ans;
 
    cin >> n >> a >> b;

    x = a-1; y = n-a; z = n-b+1;

    mem(dp,-1);
    ans = f(x,y,z,0);
	
	mem(dp,-1);
	ans = (ans + f(x,y,z,1)) % mod;

	cout << ans << endl;
 
    return 0;
}

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