oj.uz

Submission #1005528

# Submission time Handle Problem Language Result Execution time Memory
1005528 2024-06-22T14:56:26 Z vqpahmad Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 536 ms 70992 KB 
#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 202;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int dp[MAXN][MAXN][MAXN][2];
int n, cs, cf;
void solve(){
	dp[1][1][1][0] = dp[1][1][1][1] = 1;
	for (int i = 2; i <= n ; i++){
		for (int j = 1; j <= i; j++){
			for (int k = 1; k <= i; k++){
				if (j == k) continue;
				for (int l = 1; l < k; l++){
					dp[i][j][k][1] += dp[i - 1][j - (k <= j)][l][0];
					if (dp[i][j][k][1] >= mod) dp[i][j][k][1] -= mod;
				}
				for (int l = k; l <= i; l++){
					dp[i][j][k][0] += dp[i - 1][j - (k <= j)][l][1];
					if (dp[i][j][k][0] >= mod) dp[i][j][k][0] -= mod;
				}
			}
		}
	}
	//for (int i = 1; i <= n; i++){
		//for (int j = 1; j <= n; j++){
			//debug(i, j, dp[n][i][j][0] + dp[n][i][j][1]);
			//cout << dp[n][i][j][0] + dp[n][i][j][1] << ' ';
		//}
		//cout << endl;
	//}
	cout << (dp[n][cs][cf][0] + dp[n][cs][cf][1]) % mod << endl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> cs >> cf;
	solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 2 ms 3548 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 2 ms 3928 KB Output is correct
11 Correct 2 ms 3672 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 2 ms 3548 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 2 ms 3928 KB Output is correct
11 Correct 2 ms 3672 KB Output is correct
12 Correct 492 ms 34364 KB Output is correct
13 Correct 371 ms 30984 KB Output is correct
14 Correct 446 ms 34384 KB Output is correct
15 Correct 518 ms 34812 KB Output is correct
16 Correct 467 ms 34644 KB Output is correct
17 Correct 461 ms 34896 KB Output is correct
18 Correct 340 ms 28044 KB Output is correct
19 Correct 425 ms 33872 KB Output is correct
20 Correct 517 ms 34740 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 2 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 2 ms 3676 KB Output is correct
7 Correct 2 ms 3548 KB Output is correct
8 Correct 2 ms 3676 KB Output is correct
9 Correct 2 ms 3676 KB Output is correct
10 Correct 2 ms 3928 KB Output is correct
11 Correct 2 ms 3672 KB Output is correct
12 Correct 492 ms 34364 KB Output is correct
13 Correct 371 ms 30984 KB Output is correct
14 Correct 446 ms 34384 KB Output is correct
15 Correct 518 ms 34812 KB Output is correct
16 Correct 467 ms 34644 KB Output is correct
17 Correct 461 ms 34896 KB Output is correct
18 Correct 340 ms 28044 KB Output is correct
19 Correct 425 ms 33872 KB Output is correct
20 Correct 517 ms 34740 KB Output is correct
21 Runtime error 536 ms 70992 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -