oj.uz

Submission #105363

# Submission time Handle Problem Language Result Execution time Memory
105363 2019-04-11T14:34:46 Z the_art_of_war Kangaroo (CEOI16_kangaroo) C++14
100 / 100
 147 ms 64764 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;

ll 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 = dp[i][comp][le][ri];
    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 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 60 ms 64504 KB Output is correct
2 Correct 53 ms 64504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 64504 KB Output is correct
2 Correct 53 ms 64504 KB Output is correct
3 Correct 60 ms 64504 KB Output is correct
4 Correct 54 ms 64460 KB Output is correct
5 Correct 59 ms 64540 KB Output is correct
6 Correct 56 ms 64504 KB Output is correct
7 Correct 54 ms 64476 KB Output is correct
8 Correct 59 ms 64504 KB Output is correct
9 Correct 53 ms 64564 KB Output is correct
10 Correct 54 ms 64504 KB Output is correct
11 Correct 55 ms 64632 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 64504 KB Output is correct
2 Correct 53 ms 64504 KB Output is correct
3 Correct 60 ms 64504 KB Output is correct
4 Correct 54 ms 64460 KB Output is correct
5 Correct 59 ms 64540 KB Output is correct
6 Correct 56 ms 64504 KB Output is correct
7 Correct 54 ms 64476 KB Output is correct
8 Correct 59 ms 64504 KB Output is correct
9 Correct 53 ms 64564 KB Output is correct
10 Correct 54 ms 64504 KB Output is correct
11 Correct 55 ms 64632 KB Output is correct
12 Correct 53 ms 64476 KB Output is correct
13 Correct 53 ms 64504 KB Output is correct
14 Correct 56 ms 64504 KB Output is correct
15 Correct 57 ms 64504 KB Output is correct
16 Correct 55 ms 64504 KB Output is correct
17 Correct 58 ms 64604 KB Output is correct
18 Correct 57 ms 64632 KB Output is correct
19 Correct 56 ms 64504 KB Output is correct
20 Correct 55 ms 64632 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 64504 KB Output is correct
2 Correct 53 ms 64504 KB Output is correct
3 Correct 60 ms 64504 KB Output is correct
4 Correct 54 ms 64460 KB Output is correct
5 Correct 59 ms 64540 KB Output is correct
6 Correct 56 ms 64504 KB Output is correct
7 Correct 54 ms 64476 KB Output is correct
8 Correct 59 ms 64504 KB Output is correct
9 Correct 53 ms 64564 KB Output is correct
10 Correct 54 ms 64504 KB Output is correct
11 Correct 55 ms 64632 KB Output is correct
12 Correct 53 ms 64476 KB Output is correct
13 Correct 53 ms 64504 KB Output is correct
14 Correct 56 ms 64504 KB Output is correct
15 Correct 57 ms 64504 KB Output is correct
16 Correct 55 ms 64504 KB Output is correct
17 Correct 58 ms 64604 KB Output is correct
18 Correct 57 ms 64632 KB Output is correct
19 Correct 56 ms 64504 KB Output is correct
20 Correct 55 ms 64632 KB Output is correct
21 Correct 66 ms 64632 KB Output is correct
22 Correct 66 ms 64604 KB Output is correct
23 Correct 64 ms 64640 KB Output is correct
24 Correct 146 ms 64764 KB Output is correct
25 Correct 147 ms 64760 KB Output is correct
26 Correct 133 ms 64760 KB Output is correct
27 Correct 141 ms 64760 KB Output is correct
28 Correct 102 ms 64632 KB Output is correct