oj.uz

Submission #444164

# Submission time Handle Problem Language Result Execution time Memory
444164 2021-07-13T08:24:10 Z prvocislo Kangaroo (CEOI16_kangaroo) C++17
100 / 100
 52 ms 15948 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll mod = 1e9 + 7;
int add(int a, int b) { return (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % mod; }
void upd(int &a, int b) { a = (a + b) % mod; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, s, f;
    cin >> n >> s >> f; 
    vector<vector<int> > dp(n+2, vector<int>(n+2, 0)); // dp[number of vertices][number of components]
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
    {
        if (i == s || i == f)
        {
            upd(dp[i][j], dp[i-1][j-1]); // bud pridame jeden novy komponent
            int c = (j - (s < i) - (f < i));
            if (i == n) c++;
            upd(dp[i][j], mul(dp[i-1][j], c)); // alebo sa napojime na nejaky predosly
        }
        else 
        {
            upd(dp[i][j], dp[i-1][j-1]); // bud pridame jeden novy komponent
            // ideme spojit dva ine komponenty. s a f mozeme (dokonca musime) spojit len ak i == n.
            if (i == n)
            {
                upd(dp[i][j], dp[i-1][j+1]);
            }
            else
            {
                int c1 = (s < i) + (f < i), c2 = j + 1 - c1;
                int val = (c2 * (c2 - 1)) + c1 * c2;
                upd(dp[i][j], mul(dp[i-1][j+1], val));
            }
        }
        //cout << dp[i][j] << " ";
        //if (j == n) cout << endl;
    }
    cout << dp[n][1] << "\n";
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 5 ms 1996 KB Output is correct
22 Correct 6 ms 2252 KB Output is correct
23 Correct 9 ms 2488 KB Output is correct
24 Correct 52 ms 15948 KB Output is correct
25 Correct 45 ms 15948 KB Output is correct
26 Correct 45 ms 15948 KB Output is correct
27 Correct 45 ms 15820 KB Output is correct
28 Correct 26 ms 9180 KB Output is correct