Submission #48012

#	Time	Username	Problem	Language	Result	Execution time	Memory
48012		robert	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	106 ms	145400 KiB

kangaroo

#include <iostream>
#include <cstring>

using namespace std;

const int maxN = 210;
const int MOD = 1000000007; 

int m[maxN][maxN][maxN][4];
//cf shows the number of things before finish tile
int solve(int before, int after, int cf, int dir){
//	cout << before << " " << after << " " << cf << " " << dir << endl;
	if(after+before==1){
		if(dir==1&&cf==0&&after==1){
			//so we hop to second to last cell, the back to first cell
			return 1;
		} else if(dir==-1&&cf==1&&before==1){
			//we hop to second to last cell, then forward to finish cell
			return 1;
		} else {
			return 0;
		}
	}
	if(m[before][after][cf][dir+2]!=-1){
		return m[before][after][cf][dir+2];
	}
	m[before][after][cf][dir+2] = 0;
	if(dir==-1||dir==0){
		//must go backwards, towards 0
		int z = cf;
		for(int x=before-1, y=after; x>=0; x--, y++){
			if(x<cf)
				z = cf-1;
			m[before][after][cf][dir+2] += solve(x, y, z, 1);
			m[before][after][cf][dir+2] %= MOD;
		}
	}
	if(dir==1||dir==0){
		//must go forward
		int z = cf;
		for(int x=after-1, y=before; x>=0; x--, y++){
			if(y<cf)
				z = cf-1;
			m[before][after][cf][dir+2] += solve(y, x, z, -1);
			m[before][after][cf][dir+2] %= MOD;
		}
	}
	return m[before][after][cf][dir+2]%MOD;
}

int main(){
	int N, cs, cf;
	cin>>N>>cs>>cf;
	if(N<=3){
		cout << 1 << endl;
		return 0;
	}
	memset(m, -1, sizeof(m));
	int bef = cs-1, aft = N-cs;
	if(cf>cs)
		aft--;
	else
		bef--;
	int cz = cf-1;
	if(cs<cf){
		cz--;
	}
	cout << solve(bef, aft, cz, 0) << endl;
	return 0;
}

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