oj.uz

Submission #410247

# Submission time Handle Problem Language Result Execution time Memory
410247 2021-05-22T11:01:59 Z Blagojce Kangaroo (CEOI16_kangaroo) C++11
51 / 100
 951 ms 523596 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define all(v) begin(v), end(v)
#define pq priority_queue
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const ll inf = 1e18;
const ll mod = 1e9+7;
const int mxn = 2e5;


int n, f, s;
int p = 0;

ll dp[202][202][202][2][2];

ll g(int a, int b, int pos, int side){
	
	if(dp[a][b][pos][side][p] != -1) return dp[a][b][pos][side][p];
	
	int dir = ((a+b)&1)^p;
	ll ret = 0;
	if(side == 0){
		if(dir == 0){
			if(b == 0 && a == 1){
				return 0;
			}
			
			fr(ipos, 0, pos){
				ret += g(a-1, b, ipos, 0);
				ret %= mod;
			}
		}
		else{
			if(b == 0 && a == 1){
				return 1;
			}
			
			fr(ipos, pos, a-1){
				ret += g(a-1, b, ipos, 0);
				ret %= mod;
			}
			fr(ipos, 0, b){
				ret += g(a-1, b, ipos, 1);
				ret %= mod;
			}
		}
	}
	else{
		if(dir == 1){
			if(a == 0 && b == 1){
				return 0;
			}
			
			fr(ipos, pos, b-1){
				ret += g(a, b-1, ipos, 1);
				ret %= mod;
			}
		}
		else{
			if(a == 0 && b == 1){
				return 1;
			}
			
			fr(ipos, 0, pos){
				ret += g(a, b-1, ipos, 1);
				ret %= mod;
			}
			fr(ipos, 0, a){
				ret += g(a, b-1, ipos, 0);
				ret %= mod;
			}
		}
	}
	dp[a][b][pos][side][p] = ret;
	return ret;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> s >> f;
	
	if(s > f) swap(s, f);
	--s, --f;
	memset(dp, -1, sizeof(dp));
	
	int A = f;
	int B = n-A-1;
	ll tot = g(A, B, s, 0);
	p = 1;
	tot += g(A, B, s, 0);
	tot %= mod;
	cout<<tot<<endl;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 258360 KB Output is correct
2 Correct 112 ms 258296 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 258360 KB Output is correct
2 Correct 112 ms 258296 KB Output is correct
3 Correct 107 ms 258272 KB Output is correct
4 Correct 108 ms 258372 KB Output is correct
5 Correct 109 ms 258356 KB Output is correct
6 Correct 109 ms 258264 KB Output is correct
7 Correct 108 ms 258356 KB Output is correct
8 Correct 108 ms 258248 KB Output is correct
9 Correct 108 ms 258352 KB Output is correct
10 Correct 106 ms 258248 KB Output is correct
11 Correct 107 ms 258320 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 258360 KB Output is correct
2 Correct 112 ms 258296 KB Output is correct
3 Correct 107 ms 258272 KB Output is correct
4 Correct 108 ms 258372 KB Output is correct
5 Correct 109 ms 258356 KB Output is correct
6 Correct 109 ms 258264 KB Output is correct
7 Correct 108 ms 258356 KB Output is correct
8 Correct 108 ms 258248 KB Output is correct
9 Correct 108 ms 258352 KB Output is correct
10 Correct 106 ms 258248 KB Output is correct
11 Correct 107 ms 258320 KB Output is correct
12 Correct 945 ms 258384 KB Output is correct
13 Correct 561 ms 258324 KB Output is correct
14 Correct 133 ms 258340 KB Output is correct
15 Correct 855 ms 258384 KB Output is correct
16 Correct 951 ms 258380 KB Output is correct
17 Correct 893 ms 258384 KB Output is correct
18 Correct 305 ms 258372 KB Output is correct
19 Correct 899 ms 258492 KB Output is correct
20 Correct 946 ms 258504 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 258360 KB Output is correct
2 Correct 112 ms 258296 KB Output is correct
3 Correct 107 ms 258272 KB Output is correct
4 Correct 108 ms 258372 KB Output is correct
5 Correct 109 ms 258356 KB Output is correct
6 Correct 109 ms 258264 KB Output is correct
7 Correct 108 ms 258356 KB Output is correct
8 Correct 108 ms 258248 KB Output is correct
9 Correct 108 ms 258352 KB Output is correct
10 Correct 106 ms 258248 KB Output is correct
11 Correct 107 ms 258320 KB Output is correct
12 Correct 945 ms 258384 KB Output is correct
13 Correct 561 ms 258324 KB Output is correct
14 Correct 133 ms 258340 KB Output is correct
15 Correct 855 ms 258384 KB Output is correct
16 Correct 951 ms 258380 KB Output is correct
17 Correct 893 ms 258384 KB Output is correct
18 Correct 305 ms 258372 KB Output is correct
19 Correct 899 ms 258492 KB Output is correct
20 Correct 946 ms 258504 KB Output is correct
21 Runtime error 362 ms 523596 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -