oj.uz

Submission #447169

# Submission time Handle Problem Language Result Execution time Memory
447169 2021-07-24T20:49:07 Z Chy_Chy Zapina (COCI20_zapina) C++14
110 / 110
 533 ms 2628 KB 
#include<bits/stdc++.h>
using namespace std;

#include<ext/pb_ds/assoc_container.hpp> // common file
#include<ext/pb_ds/tree_policy.hpp> // including tree_order_statistics_node_update

using namespace __gnu_pbds;


#define int             long long
#define pb              push_back
#define ppb             pop_back
#define pf              push_front
#define ppf             pop_front
#define all(x)          (x).begin(), (x).end()
#define uniq(v)         (v).erase(unique(all(v)), (v).end())
#define sz(x)           (int)((x).size())
#define ff              first
#define ss              second
#define rep(i, a, b)    for(int i = a; i <= b; i++)
#define mem1(a)         memset(a, -1, sizeof(a))
#define mem0(a)         memset(a, 0, sizeof(a))
#define endl            "\n"
#define debug(x)        cerr << #x << " == " << (x) << '\n';
#define YES             cout << "YES\n"
#define NO              cout << "NO\n"
#define nn              "\n"

// bit manipulation
#define SetBit(x, k)    (x |= (1LL << k))
#define ClearBit(x, k)  (x &= ~(1LL << k))
#define CheckBit(x, k)  (x & (1LL << k))


typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

#define ordered_set tree<int, null_type, less<int> , rb_tree_tag, tree_order_statistics_node_update>

const long long INF = 1e18;
const int32_t M = 1e9 + 7;
const int32_t MM = 998244353;


int binpow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = a * res;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}


void fast_io()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
int gcd(int a, int b) {if (b == 0) return a; return gcd(b, a % b);}
int lcm(int a, int b) {return a / gcd(a, b) * b;}


const int N = 400;


#define PRIME   M

int binpow(int a, int b = M - 2, int MOD = M) {
    int res = 1;
    while (b > 0) {
        if (b & 1) {
            res = a * res % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int fact[N], invfact[N];


void init() {

    int p = PRIME;
    fact[0] = 1;

    int i;
    for (i = 1; i < N; i++) {
        fact[i] = i * fact[i - 1] % p;

    }

    i--;
    invfact[i] = binpow(fact[i], p - 2, p);

    for (i--; i >= 0; i--) {
        invfact[i] = invfact[i + 1] * (i + 1) % p;
    }


}

int ncr(int n, int r) {

    if (r > n || n < 0 || r < 0) return 0;

    return fact[n] * invfact[r] % PRIME * invfact[n - r] % PRIME;
}


int mem[N][N][2];

int n;


int dp(int prog, int baki, int happy) {
    if (prog > n) {
        if (baki == 0 && happy == 1) {
            return 1;
        }
        return 0;
    }
    // debug(prog);
    // debug(baki);
    int &ans = mem[prog][baki][happy];

    if (ans != -1) return ans;

    ans = 0;
    int res;
    for (int i = 0; i <= baki; i++) {
        if (i == prog) {
            res = (ncr(baki, i) * dp(prog + 1, baki - i, 1)) % M;
            ans = (ans + res) % M;
        }
        else {
            res = (ncr(baki, i) * dp(prog + 1, baki - i, happy)) % M;
            ans = (ans + res) % M;
        }
    }

    return ans;
}
void KhelaFinal() {
    cin >> n;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k < 2; k++) {
                mem[i][j][k] = -1;
            }
        }
    }


    cout << dp(1, n, 0) << endl;



}

signed main()
{
    fast_io();
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
    int t = 1;

    // cin >> t;
    init();

    while (t--) {

        KhelaFinal();


    }
    return 0;


}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
33.0 / 33.0

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

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 253 ms 1996 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 54 ms 1336 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 339 ms 2224 KB Output is correct
22 Correct 38 ms 1228 KB Output is correct
23 Correct 4 ms 588 KB Output is correct
24 Correct 72 ms 1356 KB Output is correct
25 Correct 50 ms 1296 KB Output is correct
26 Correct 99 ms 1588 KB Output is correct
27 Correct 483 ms 2476 KB Output is correct
28 Correct 500 ms 2500 KB Output is correct
29 Correct 490 ms 2480 KB Output is correct
30 Correct 500 ms 2492 KB Output is correct
31 Correct 501 ms 2560 KB Output is correct
32 Correct 508 ms 2508 KB Output is correct
33 Correct 511 ms 2628 KB Output is correct
34 Correct 515 ms 2508 KB Output is correct
35 Correct 516 ms 2532 KB Output is correct
36 Correct 524 ms 2628 KB Output is correct
37 Correct 533 ms 2528 KB Output is correct