oj.uz

Submission #261279

# Submission time Handle Problem Language Result Execution time Memory
261279 2020-08-11T15:48:33 Z super_j6 Kangaroo (CEOI16_kangaroo) C++14
36 / 100
 2000 ms 273880 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
 
const int mod = 1000000007;
const int mxn = 2001;
int n, x, y;
unordered_map<int, int> dp[mxn][mxn];
 
int sol(int n, int x, int y){
 	if(dp[n][x].count(y)) return dp[n][x][y];
	int ret = 0;
	for(int i = (n & 1) * (x + 1); i < (n & 1 ? n : x); i++){
		if(i != y) (ret += sol(n - 1, i - (n & 1), y - (x < y))) %= mod;
	}
	return dp[n][x][y] = ret;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	for(int i = 0; i < 2; i++)
	for(int j = 0; j < 2; j++){
		dp[2][i][j] = 0;
	}
	dp[2][1][0] = 1;
	
	cin >> n >> x >> y;
	x--, y--;
	
	int ret = (sol(n, x, y) + sol(n, n - x - 1, n - y - 1)) % mod;
	
	cout << ret << endl;
 
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 219768 KB Output is correct
2 Correct 171 ms 219728 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 219768 KB Output is correct
2 Correct 171 ms 219728 KB Output is correct
3 Correct 150 ms 219768 KB Output is correct
4 Correct 171 ms 220028 KB Output is correct
5 Correct 172 ms 219768 KB Output is correct
6 Correct 175 ms 220152 KB Output is correct
7 Correct 175 ms 220152 KB Output is correct
8 Correct 171 ms 220024 KB Output is correct
9 Correct 170 ms 220024 KB Output is correct
10 Correct 173 ms 220164 KB Output is correct
11 Correct 172 ms 220024 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 219768 KB Output is correct
2 Correct 171 ms 219728 KB Output is correct
3 Correct 150 ms 219768 KB Output is correct
4 Correct 171 ms 220028 KB Output is correct
5 Correct 172 ms 219768 KB Output is correct
6 Correct 175 ms 220152 KB Output is correct
7 Correct 175 ms 220152 KB Output is correct
8 Correct 171 ms 220024 KB Output is correct
9 Correct 170 ms 220024 KB Output is correct
10 Correct 173 ms 220164 KB Output is correct
11 Correct 172 ms 220024 KB Output is correct
12 Execution timed out 2100 ms 273880 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 219768 KB Output is correct
2 Correct 171 ms 219728 KB Output is correct
3 Correct 150 ms 219768 KB Output is correct
4 Correct 171 ms 220028 KB Output is correct
5 Correct 172 ms 219768 KB Output is correct
6 Correct 175 ms 220152 KB Output is correct
7 Correct 175 ms 220152 KB Output is correct
8 Correct 171 ms 220024 KB Output is correct
9 Correct 170 ms 220024 KB Output is correct
10 Correct 173 ms 220164 KB Output is correct
11 Correct 172 ms 220024 KB Output is correct
12 Execution timed out 2100 ms 273880 KB Time limit exceeded
13 Halted 0 ms 0 KB -