제출 #48009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
48009		robert	캥거루 (CEOI16_kangaroo)	C++14	0 / 100	2 ms	248 KiB

kangaroo

#include <iostream>
#include <cstring>

using namespace std;

const int maxN = 500;

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);
		}
	}
	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);
		}
	}
	return m[before][after][cf][dir+2];
}

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