oj.uz

Submission #30837

# Submission time Handle Problem Language Result Execution time Memory
30837 2017-07-27T14:19:48 Z szawinis Kangaroo (CEOI16_kangaroo) C++14
0 / 100
 0 ms 17820 KB 
#include <bits/stdc++.h>
using namespace std;
const long long MOD = (1e9)+7;

inline void add(int& a, int b) { a = (a + b) % MOD; }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }

int n, s, e, dp[2001][2001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> s >> e;
	dp[0][0] = 1;
	for(int i = 0; i < n; i++) for(int j = 0; j <= i; j++) {
		if(i+1 == s || i+1 == e) { // automatically decrease j by 1, since s, e not counted
			add(dp[i+1][j], dp[i][j]); // new cc
			if(j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to start/end of some cc
		} else {
			add(dp[i+1][j+1], dp[i][j]); // new cc
			if(j) add(dp[i+1][j-1], mul(dp[i][j], j*(j-1))); // join two non-empty cc
			if(i+1 > s && j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to start's cc
			if(i+1 > e && j) add(dp[i+1][j-1], mul(dp[i][j], j)); // append to end's cc
		}
	}
	cout << dp[n][0];
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17820 KB Output is correct
2 Incorrect 0 ms 17820 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17820 KB Output is correct
2 Incorrect 0 ms 17820 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17820 KB Output is correct
2 Incorrect 0 ms 17820 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17820 KB Output is correct
2 Incorrect 0 ms 17820 KB Output isn't correct