oj.uz

Submission #685022

# Submission time Handle Problem Language Result Execution time Memory
685022 2023-01-23T05:43:54 Z NeroZein Kangaroo (CEOI16_kangaroo) C++14
100 / 100
 21 ms 352 KB 
/*
 *    author: NeroZein
 *    created: 23.01.2023 08:16:46
*/
#include <bits/stdc++.h>
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int md = 1e9+7;

inline int add(int a, int b){
	a += b;
	if(a >= md){
		a -= md;
	}
	return a;
}

inline int mul(int a, int b){
	return (int)((long long) a * b % md);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, cs, cf;
	cin >> n >> cs >> cf;
	vector<int> dp(n);
	dp[1] = 1; 
	for (int i = 2; i <= n; ++i){
		vector<int> pd(n); 
		for (int j = 1; j < n; ++j){
			//endpoint either 
			if(i == cs || i == cf){
				//alone or to the left or right to existing set
				pd[j] = add(dp[j-1], dp[j]);
			}
			else{
				//merge two sets or start a new one
				pd[j] = add(mul(j, dp[j+1]), mul(j - (i > cs) - (i > cf), dp[j-1]));
			}
		}
		swap(dp, pd);
	}
	cout << dp[1]; 
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 324 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 324 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 2 ms 224 KB Output is correct
22 Correct 3 ms 224 KB Output is correct
23 Correct 4 ms 352 KB Output is correct
24 Correct 20 ms 224 KB Output is correct
25 Correct 21 ms 336 KB Output is correct
26 Correct 19 ms 344 KB Output is correct
27 Correct 20 ms 352 KB Output is correct
28 Correct 11 ms 224 KB Output is correct