oj.uz

Submission #229236

# Submission time Handle Problem Language Result Execution time Memory
229236 2020-05-03T21:20:37 Z VEGAnn Zapina (COCI20_zapina) C++14
110 / 110
 182 ms 2248 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
const int md = int(1e9) + 7;
const int N = 410;
const int PW = 20;
int f[N][N][2], c[N][N], n;

int sum(int x, int y){
    x += y;
    if (x >= md)
        x -= md;
    return x;
}

int mult(int x, int y) { return (1ll * x * y) % md;}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n;

    c[0][0] = 1;

    for (int i = 1; i <= n; i++){
        c[i][0] = c[i][i] = 1;

        for (int j = 1; j < i; j++)
            c[i][j] = sum(c[i - 1][j], c[i - 1][j - 1]);
    }

    f[0][n][0] = 1;

    for (int i = 0; i < n; i++)
    for (int ost = 0; ost <= n; ost++)
    for (int tp = 0; tp < 2; tp++){
        if (f[i][ost][tp] == 0) continue;

        for (int nw = 0; nw <= ost; nw++){
            int ni = i + 1, nost = ost - nw, ntp = tp;

            if (nw == ni)
                ntp = 1;

            f[ni][nost][ntp] = sum(f[ni][nost][ntp], mult(f[i][ost][tp], c[ost][nw]));
        }
    }

    cout << f[n][0][1];

    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 87 ms 1648 KB Output is correct
18 Correct 5 ms 640 KB Output is correct
19 Correct 22 ms 1152 KB Output is correct
20 Correct 5 ms 512 KB Output is correct
21 Correct 116 ms 1884 KB Output is correct
22 Correct 17 ms 1024 KB Output is correct
23 Correct 6 ms 640 KB Output is correct
24 Correct 27 ms 1152 KB Output is correct
25 Correct 20 ms 1144 KB Output is correct
26 Correct 36 ms 1272 KB Output is correct
27 Correct 160 ms 2040 KB Output is correct
28 Correct 161 ms 1912 KB Output is correct
29 Correct 164 ms 2040 KB Output is correct
30 Correct 163 ms 2040 KB Output is correct
31 Correct 182 ms 2248 KB Output is correct
32 Correct 166 ms 2040 KB Output is correct
33 Correct 168 ms 2040 KB Output is correct
34 Correct 173 ms 2040 KB Output is correct
35 Correct 176 ms 2016 KB Output is correct
36 Correct 170 ms 2016 KB Output is correct
37 Correct 176 ms 2040 KB Output is correct