oj.uz

Submission #194125

# Submission time Handle Problem Language Result Execution time Memory
194125 2020-01-15T16:46:55 Z toma Kangaroo (CEOI16_kangaroo) C++14
100 / 100
 115 ms 31992 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint MOD = 1e9 + 7;
 
int N, S, T;
lint memo[2005][2005];
 
lint dp(int n, int comp) {
    if (comp < 0) { 
        return 0; 
    }
    if (n == N - 1) { 
        return comp == 0; // use last piece to merge S and T component
    }
    if (memo[n][comp] != -1) {
        return memo[n][comp];
    }
 
    lint &res = memo[n][comp] = 0;
 
    if (n == S || n == T) {
        res += dp(n + 1, comp); // add S or T as new component
        res += comp * dp(n + 1, comp - 1); // mege with free component
    } else {
        res += dp(n + 1, comp + 1); // add new component
        res += comp * (comp - 1) * dp(n + 1, comp - 1); // merge two free components
        if (n > S) { // merge start with free
            res += comp * dp(n + 1, comp - 1); // append S to a component, and it cannot be modified further
        }
        if (n > T) { // merge end with free
            res += comp * dp(n + 1, comp - 1); // append T to a component, and it cannot be modified further
        }
    }
 
    res %= MOD;
    return res;
}
 
int main() {
    memset(memo, -1, sizeof(memo));
    cin >> N >> S >> T;
    S--, T--;
    cout << dp(0, 0) << "\n";
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31736 KB Output is correct
2 Correct 29 ms 31736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31736 KB Output is correct
2 Correct 29 ms 31736 KB Output is correct
3 Correct 27 ms 31864 KB Output is correct
4 Correct 29 ms 31864 KB Output is correct
5 Correct 29 ms 31736 KB Output is correct
6 Correct 29 ms 31708 KB Output is correct
7 Correct 29 ms 31736 KB Output is correct
8 Correct 29 ms 31864 KB Output is correct
9 Correct 29 ms 31864 KB Output is correct
10 Correct 35 ms 31864 KB Output is correct
11 Correct 26 ms 31740 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31736 KB Output is correct
2 Correct 29 ms 31736 KB Output is correct
3 Correct 27 ms 31864 KB Output is correct
4 Correct 29 ms 31864 KB Output is correct
5 Correct 29 ms 31736 KB Output is correct
6 Correct 29 ms 31708 KB Output is correct
7 Correct 29 ms 31736 KB Output is correct
8 Correct 29 ms 31864 KB Output is correct
9 Correct 29 ms 31864 KB Output is correct
10 Correct 35 ms 31864 KB Output is correct
11 Correct 26 ms 31740 KB Output is correct
12 Correct 32 ms 31840 KB Output is correct
13 Correct 29 ms 31736 KB Output is correct
14 Correct 29 ms 31736 KB Output is correct
15 Correct 30 ms 31864 KB Output is correct
16 Correct 31 ms 31908 KB Output is correct
17 Correct 30 ms 31736 KB Output is correct
18 Correct 28 ms 31824 KB Output is correct
19 Correct 30 ms 31736 KB Output is correct
20 Correct 30 ms 31864 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 31736 KB Output is correct
2 Correct 29 ms 31736 KB Output is correct
3 Correct 27 ms 31864 KB Output is correct
4 Correct 29 ms 31864 KB Output is correct
5 Correct 29 ms 31736 KB Output is correct
6 Correct 29 ms 31708 KB Output is correct
7 Correct 29 ms 31736 KB Output is correct
8 Correct 29 ms 31864 KB Output is correct
9 Correct 29 ms 31864 KB Output is correct
10 Correct 35 ms 31864 KB Output is correct
11 Correct 26 ms 31740 KB Output is correct
12 Correct 32 ms 31840 KB Output is correct
13 Correct 29 ms 31736 KB Output is correct
14 Correct 29 ms 31736 KB Output is correct
15 Correct 30 ms 31864 KB Output is correct
16 Correct 31 ms 31908 KB Output is correct
17 Correct 30 ms 31736 KB Output is correct
18 Correct 28 ms 31824 KB Output is correct
19 Correct 30 ms 31736 KB Output is correct
20 Correct 30 ms 31864 KB Output is correct
21 Correct 36 ms 31964 KB Output is correct
22 Correct 33 ms 31864 KB Output is correct
23 Correct 38 ms 31876 KB Output is correct
24 Correct 102 ms 31992 KB Output is correct
25 Correct 94 ms 31864 KB Output is correct
26 Correct 103 ms 31980 KB Output is correct
27 Correct 115 ms 31992 KB Output is correct
28 Correct 57 ms 31992 KB Output is correct