oj.uz

Submission #917178

# Submission time Handle Problem Language Result Execution time Memory
917178 2024-01-27T11:34:44 Z KiaRez Kangaroo (CEOI16_kangaroo) C++17
51 / 100
 67 ms 134608 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int ln, s, f, mark[205][205][205][2];
ll mp[205][205][205][2];

ll calc(int n, int i, int j, int flg=0) {
	if(min(i, j)<=0 || max(i, j)>n || i==j) return 0;
	if(n==2) {
		if(i<j&&flg==0) return 1;
		if(i>j&&flg==1) return 1;
		return 0;
	}
	if(i > j) {
		if((n-1)%2 == 1) return calc(n, j, i, 1-flg);
		return calc(n, j, i, flg);
	}

	if(mark[n][i][j][flg] == 1) return mp[n][i][j][flg];
	
	ll res = 0;
	if(flg == 0) {
		if(i==j-1) {
			for(int k=i+1; k<=n-1; k++) res = MOD(res + calc(n-1, k, j-1, 1));
		} else {
			res = MOD(calc(n, i+1, j, 0) + calc(n-1, i, j-1, 1));
		}
	} else {
		res = MOD(res + calc(n, i-1, j, 1) + calc(n-1, i-1, j-1, 0));
	}
	mp[n][i][j][flg] = res, mark[n][i][j][flg] = 1;
	return res;
}

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

	cin>>ln>>s>>f;
	//fuck(calc(3, 3, 2, 1));
	//fuck(calc(ln, s, f, 0));
	cout<<MOD(calc(ln, s, f, 0) + calc(ln, s, f, 1));

	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 4 ms 19548 KB Output is correct
4 Correct 5 ms 28364 KB Output is correct
5 Correct 5 ms 28508 KB Output is correct
6 Correct 5 ms 28664 KB Output is correct
7 Correct 5 ms 26204 KB Output is correct
8 Correct 5 ms 28660 KB Output is correct
9 Correct 5 ms 28248 KB Output is correct
10 Correct 7 ms 28504 KB Output is correct
11 Correct 5 ms 28252 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 4 ms 19548 KB Output is correct
4 Correct 5 ms 28364 KB Output is correct
5 Correct 5 ms 28508 KB Output is correct
6 Correct 5 ms 28664 KB Output is correct
7 Correct 5 ms 26204 KB Output is correct
8 Correct 5 ms 28660 KB Output is correct
9 Correct 5 ms 28248 KB Output is correct
10 Correct 7 ms 28504 KB Output is correct
11 Correct 5 ms 28252 KB Output is correct
12 Correct 67 ms 131420 KB Output is correct
13 Correct 53 ms 127896 KB Output is correct
14 Correct 31 ms 134608 KB Output is correct
15 Correct 56 ms 134228 KB Output is correct
16 Correct 58 ms 133204 KB Output is correct
17 Correct 60 ms 134352 KB Output is correct
18 Correct 37 ms 124564 KB Output is correct
19 Correct 65 ms 133204 KB Output is correct
20 Correct 64 ms 134452 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 4 ms 19548 KB Output is correct
4 Correct 5 ms 28364 KB Output is correct
5 Correct 5 ms 28508 KB Output is correct
6 Correct 5 ms 28664 KB Output is correct
7 Correct 5 ms 26204 KB Output is correct
8 Correct 5 ms 28660 KB Output is correct
9 Correct 5 ms 28248 KB Output is correct
10 Correct 7 ms 28504 KB Output is correct
11 Correct 5 ms 28252 KB Output is correct
12 Correct 67 ms 131420 KB Output is correct
13 Correct 53 ms 127896 KB Output is correct
14 Correct 31 ms 134608 KB Output is correct
15 Correct 56 ms 134228 KB Output is correct
16 Correct 58 ms 133204 KB Output is correct
17 Correct 60 ms 134352 KB Output is correct
18 Correct 37 ms 124564 KB Output is correct
19 Correct 65 ms 133204 KB Output is correct
20 Correct 64 ms 134452 KB Output is correct
21 Runtime error 5 ms 348 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -