oj.uz

Submission #385919

# Submission time Handle Problem Language Result Execution time Memory
385919 2021-04-05T08:23:06 Z Vladth11 Kangaroo (CEOI16_kangaroo) C++14
100 / 100
 40 ms 23040 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 201;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;

ll dp[2001][2001];

void add(ll &x, ll v) {
    x += v;
    x %= MOD;
}

int main() {
    int n, a, b, i;
    cin >> n >> a >> b;
    dp[1][1] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            if(i == a) {
                add(dp[i][j], dp[i - 1][j]);///adaugam ori la ce mai din stanga componenta
                add(dp[i][j], dp[i - 1][j - 1]); ///ori ne facem noi o componenta noua
            } else if(i == b) {
                ///same story ca la a
                add(dp[i][j], dp[i - 1][j]);
                add(dp[i][j], dp[i - 1][j - 1]);
            } else {
                add(dp[i][j], (dp[i - 1][j + 1] * j) % MOD); ///mergeuim doua
                add(dp[i][j], (dp[i - 1][j - 1] * ((j - 2) + (i < a) + (i < b))) % MOD); ///facem o comp noua
            }
        }
    }
    cout << dp[n][1];
    return 0;
}

Compilation message

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:29:18: warning: unused variable 'i' [-Wunused-variable]
   29 |     int n, a, b, i;
      |                  ^

Subtask #1
6.0 / 6.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 2 ms 1260 KB Output is correct
14 Correct 2 ms 1260 KB Output is correct
15 Correct 2 ms 1260 KB Output is correct
16 Correct 2 ms 1260 KB Output is correct
17 Correct 2 ms 1260 KB Output is correct
18 Correct 2 ms 1132 KB Output is correct
19 Correct 2 ms 1260 KB Output is correct
20 Correct 2 ms 1260 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 2 ms 1260 KB Output is correct
14 Correct 2 ms 1260 KB Output is correct
15 Correct 2 ms 1260 KB Output is correct
16 Correct 2 ms 1260 KB Output is correct
17 Correct 2 ms 1260 KB Output is correct
18 Correct 2 ms 1132 KB Output is correct
19 Correct 2 ms 1260 KB Output is correct
20 Correct 2 ms 1260 KB Output is correct
21 Correct 6 ms 4716 KB Output is correct
22 Correct 7 ms 5100 KB Output is correct
23 Correct 7 ms 5632 KB Output is correct
24 Correct 40 ms 23020 KB Output is correct
25 Correct 34 ms 23020 KB Output is correct
26 Correct 39 ms 23040 KB Output is correct
27 Correct 34 ms 22892 KB Output is correct
28 Correct 24 ms 15084 KB Output is correct