oj.uz

Submission #48039

# Submission time Handle Problem Language Result Execution time Memory
48039 2018-05-09T13:53:42 Z robert Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 1071 ms 290984 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;
			else
				z = cf;
			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;
			else
				z = cf;
			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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 145272 KB Output is correct
2 Correct 103 ms 145384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 145272 KB Output is correct
2 Correct 103 ms 145384 KB Output is correct
3 Correct 104 ms 145460 KB Output is correct
4 Correct 105 ms 145460 KB Output is correct
5 Correct 104 ms 145472 KB Output is correct
6 Correct 105 ms 145476 KB Output is correct
7 Correct 104 ms 145608 KB Output is correct
8 Correct 103 ms 145668 KB Output is correct
9 Correct 105 ms 145760 KB Output is correct
10 Correct 107 ms 145760 KB Output is correct
11 Correct 101 ms 145760 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 145272 KB Output is correct
2 Correct 103 ms 145384 KB Output is correct
3 Correct 104 ms 145460 KB Output is correct
4 Correct 105 ms 145460 KB Output is correct
5 Correct 104 ms 145472 KB Output is correct
6 Correct 105 ms 145476 KB Output is correct
7 Correct 104 ms 145608 KB Output is correct
8 Correct 103 ms 145668 KB Output is correct
9 Correct 105 ms 145760 KB Output is correct
10 Correct 107 ms 145760 KB Output is correct
11 Correct 101 ms 145760 KB Output is correct
12 Correct 1014 ms 145760 KB Output is correct
13 Correct 639 ms 145760 KB Output is correct
14 Correct 138 ms 145760 KB Output is correct
15 Correct 977 ms 145760 KB Output is correct
16 Correct 169 ms 145760 KB Output is correct
17 Correct 1045 ms 145760 KB Output is correct
18 Correct 312 ms 145800 KB Output is correct
19 Correct 1016 ms 145800 KB Output is correct
20 Correct 1071 ms 145828 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 145272 KB Output is correct
2 Correct 103 ms 145384 KB Output is correct
3 Correct 104 ms 145460 KB Output is correct
4 Correct 105 ms 145460 KB Output is correct
5 Correct 104 ms 145472 KB Output is correct
6 Correct 105 ms 145476 KB Output is correct
7 Correct 104 ms 145608 KB Output is correct
8 Correct 103 ms 145668 KB Output is correct
9 Correct 105 ms 145760 KB Output is correct
10 Correct 107 ms 145760 KB Output is correct
11 Correct 101 ms 145760 KB Output is correct
12 Correct 1014 ms 145760 KB Output is correct
13 Correct 639 ms 145760 KB Output is correct
14 Correct 138 ms 145760 KB Output is correct
15 Correct 977 ms 145760 KB Output is correct
16 Correct 169 ms 145760 KB Output is correct
17 Correct 1045 ms 145760 KB Output is correct
18 Correct 312 ms 145800 KB Output is correct
19 Correct 1016 ms 145800 KB Output is correct
20 Correct 1071 ms 145828 KB Output is correct
21 Runtime error 255 ms 290984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -