oj.uz

Submission #94965

# Submission time Handle Problem Language Result Execution time Memory
94965 2019-01-25T22:53:11 Z jasony123123 Kangaroo (CEOI16_kangaroo) C++11
100 / 100
 38 ms 31736 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/********************CEOI 2016 Day 1 Problem 2******************************/

inline ll add(ll a, ll b) { return (a + b) % MOD; }
inline ll mul(ll a, ll b) { return (1LL * a*b) % MOD; }

int n, a, b;
ll dp[2001][2001];

int main() {
	io();
	cin >> n >> a >> b;
	dp[1][1] = 1;
	int av = 2;
	if (a == 1 || b == 1)
		av--;
	FORE(i, 2, n) {
		if (i == a || i == b) {
			av--;
			FORE(j, 1, n)
				dp[i][j] = add(dp[i - 1][j - 1], dp[i - 1][j]);
		}
		else {
			FORE(j, 1, n)
				dp[i][j] = add(dp[i - 1][j + 1] * j, dp[i - 1][j - 1] * (j - 2 + av));
		}
	}
	cout << dp[n][1] << "\n";
}

Subtask #1
6.0 / 6.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 3 ms 1528 KB Output is correct
13 Correct 3 ms 1400 KB Output is correct
14 Correct 3 ms 1400 KB Output is correct
15 Correct 2 ms 1400 KB Output is correct
16 Correct 3 ms 1660 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 3 ms 1272 KB Output is correct
19 Correct 4 ms 1400 KB Output is correct
20 Correct 3 ms 1528 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 3 ms 1528 KB Output is correct
13 Correct 3 ms 1400 KB Output is correct
14 Correct 3 ms 1400 KB Output is correct
15 Correct 2 ms 1400 KB Output is correct
16 Correct 3 ms 1660 KB Output is correct
17 Correct 3 ms 1528 KB Output is correct
18 Correct 3 ms 1272 KB Output is correct
19 Correct 4 ms 1400 KB Output is correct
20 Correct 3 ms 1528 KB Output is correct
21 Correct 7 ms 6392 KB Output is correct
22 Correct 9 ms 7032 KB Output is correct
23 Correct 8 ms 7804 KB Output is correct
24 Correct 32 ms 31684 KB Output is correct
25 Correct 32 ms 31736 KB Output is correct
26 Correct 33 ms 31608 KB Output is correct
27 Correct 38 ms 31480 KB Output is correct
28 Correct 23 ms 23800 KB Output is correct