oj.uz

Submission #105366

# Submission time Handle Problem Language Result Execution time Memory
105366 2019-04-11T14:36:03 Z the_art_of_war Kangaroo (CEOI16_kangaroo) C++14
100 / 100
 138 ms 32660 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 1e15;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 1e5 + 100;
const int LOG = 20;
const int mod = 1e9 + 7;
const int MX = 1e6 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;

int N, S, E;

int dp[2010][1020][2][2];

ll get(int i, int comp, int le, int ri) {
    if (comp < 0)
        return 0;
    if (2 * comp + 1 > N)
        return 0;
    if (dp[i][comp][le][ri] != -1)
        return dp[i][comp][le][ri];
    ll res = 0;

    if (i == N - 1) {
        if (comp == 0) {
            res = 1;
            //check
        }
        return res;
    }

    if (i == S) {
        //just
        res += get(i + 1, comp, 1, ri);
        //conn
        res += get(i + 1, comp - 1, 1, ri) * comp;

    } else if (i == E) {
        res += get(i + 1, comp, le, 1);
        res += get(i + 1, comp - 1, le, 1) * comp;
    } else {
        //just create
        res += get(i + 1, comp + 1, le, ri);
        //connect
        res += get(i + 1, comp - 1, le, ri) * (1ll * comp * (comp - 1)) % mod;

        if (le > 0) {
            //connect
            res += get(i + 1, comp - 1, le, ri) * comp;
        }
        if (ri > 0) {
            //connect
            res += get(i + 1, comp - 1, le, ri) * comp;
        }
    }
    res%=mod;
    return dp[i][comp][le][ri] = res;
}

void solve() {
    memset(dp,-1,sizeof dp);
    cin >> N >> S >> E;
    S--; E--;

    cout << get(0,0,0,0)<<"\n";

}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;

    while (t--)
        solve();
    dout << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 32504 KB Output is correct
2 Correct 30 ms 32376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 32504 KB Output is correct
2 Correct 30 ms 32376 KB Output is correct
3 Correct 31 ms 32376 KB Output is correct
4 Correct 33 ms 32448 KB Output is correct
5 Correct 31 ms 32504 KB Output is correct
6 Correct 29 ms 32504 KB Output is correct
7 Correct 33 ms 32504 KB Output is correct
8 Correct 30 ms 32508 KB Output is correct
9 Correct 30 ms 32504 KB Output is correct
10 Correct 30 ms 32512 KB Output is correct
11 Correct 30 ms 32504 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 32504 KB Output is correct
2 Correct 30 ms 32376 KB Output is correct
3 Correct 31 ms 32376 KB Output is correct
4 Correct 33 ms 32448 KB Output is correct
5 Correct 31 ms 32504 KB Output is correct
6 Correct 29 ms 32504 KB Output is correct
7 Correct 33 ms 32504 KB Output is correct
8 Correct 30 ms 32508 KB Output is correct
9 Correct 30 ms 32504 KB Output is correct
10 Correct 30 ms 32512 KB Output is correct
11 Correct 30 ms 32504 KB Output is correct
12 Correct 29 ms 32512 KB Output is correct
13 Correct 30 ms 32476 KB Output is correct
14 Correct 31 ms 32384 KB Output is correct
15 Correct 29 ms 32504 KB Output is correct
16 Correct 34 ms 32504 KB Output is correct
17 Correct 30 ms 32372 KB Output is correct
18 Correct 31 ms 32380 KB Output is correct
19 Correct 32 ms 32376 KB Output is correct
20 Correct 33 ms 32376 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 32504 KB Output is correct
2 Correct 30 ms 32376 KB Output is correct
3 Correct 31 ms 32376 KB Output is correct
4 Correct 33 ms 32448 KB Output is correct
5 Correct 31 ms 32504 KB Output is correct
6 Correct 29 ms 32504 KB Output is correct
7 Correct 33 ms 32504 KB Output is correct
8 Correct 30 ms 32508 KB Output is correct
9 Correct 30 ms 32504 KB Output is correct
10 Correct 30 ms 32512 KB Output is correct
11 Correct 30 ms 32504 KB Output is correct
12 Correct 29 ms 32512 KB Output is correct
13 Correct 30 ms 32476 KB Output is correct
14 Correct 31 ms 32384 KB Output is correct
15 Correct 29 ms 32504 KB Output is correct
16 Correct 34 ms 32504 KB Output is correct
17 Correct 30 ms 32372 KB Output is correct
18 Correct 31 ms 32380 KB Output is correct
19 Correct 32 ms 32376 KB Output is correct
20 Correct 33 ms 32376 KB Output is correct
21 Correct 42 ms 32412 KB Output is correct
22 Correct 45 ms 32464 KB Output is correct
23 Correct 51 ms 32476 KB Output is correct
24 Correct 124 ms 32632 KB Output is correct
25 Correct 114 ms 32632 KB Output is correct
26 Correct 117 ms 32660 KB Output is correct
27 Correct 138 ms 32652 KB Output is correct
28 Correct 92 ms 32640 KB Output is correct