oj.uz

Submission #48012

# Submission time Handle Problem Language Result Execution time Memory
48012 2018-05-09T11:26:21 Z robert Kangaroo (CEOI16_kangaroo) C++14
0 / 100
 106 ms 145400 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 145400 KB Output is correct
2 Incorrect 104 ms 145400 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 145400 KB Output is correct
2 Incorrect 104 ms 145400 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 145400 KB Output is correct
2 Incorrect 104 ms 145400 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 145400 KB Output is correct
2 Incorrect 104 ms 145400 KB Output isn't correct