oj.uz

Submission #554698

# Submission time Handle Problem Language Result Execution time Memory
554698 2022-04-29T08:08:39 Z alextodoran Boat (APIO16_boat) C++17
9 / 100
 1129 ms 11928 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500;
const int M_MAX = N_MAX * 4;

const int MOD = (int) 1e9 + 7;

int pwr (const int &a, const int &b) {
    if (b == 0) {
        return 1;
    } else if (b & 1) {
        return (ll) a * pwr(a, (b ^ 1)) % MOD;
    } else {
        int aux = pwr(a, (b >> 1));
        return (ll) aux * aux % MOD;
    }
}
int inv (const int &a) {
    return pwr(a, MOD - 2);
}

int N;
int a[N_MAX + 2], b[N_MAX + 2];

int M;
int l[M_MAX + 2], r[M_MAX + 2];
void compress () {
    vector <int> v;
    for (int i = 1; i <= N; i++) {
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    map <int, int> mp;
    for (int i = 0; i < (int) v.size(); i++) {
        if ((i == 0 ? 1 : v[i - 1] + 1) <= v[i] - 1) {
            M++;
            l[M] = (i == 0 ? 1 : v[i - 1] + 1);
            r[M] = v[i] - 1;
        }
        mp[v[i]] = ++M;
        l[M] = r[M] = v[i];
    }
    for (int i = 1; i <= N; i++) {
        a[i] = mp[a[i]];
        b[i] = mp[b[i]];
    }
}

int chooseVals[M_MAX + 2][N_MAX + 2];
int chooseBoxes[N_MAX + 2][N_MAX + 2];
int choose[M_MAX + 2][N_MAX + 2];
void precalc () {
    for (int cnt = 1; cnt <= N; cnt++) {
        chooseBoxes[cnt][1] = 1;
        chooseBoxes[cnt][2] = 1;
        for (int take = 3; take <= cnt; take++) {
            chooseBoxes[cnt][take] = chooseBoxes[cnt - 1][take] + chooseBoxes[cnt - 1][take - 1];
            if (chooseBoxes[cnt][take] >= MOD) {
                chooseBoxes[cnt][take] -= MOD;
            }
        }
    }
    for (int x = 1; x <= M; x++) {
        int from = r[x] - l[x] + 1;
        chooseVals[x][0] = 1;
        for (int take = 1; take <= min(N, from); take++) {
            chooseVals[x][take] = (ll) chooseVals[x][take - 1] * inv(take) % MOD * (from - (take - 1)) % MOD;
        }
        for (int cnt = 1; cnt <= N; cnt++) {
            for (int take = 1 + (cnt > 1); take <= cnt; take++) {
                choose[x][cnt] = (choose[x][cnt] + (ll) chooseVals[x][take] * chooseBoxes[cnt][take]) % MOD;
            }
        }
    }
}

int dp[N_MAX + 2][M_MAX + 2];

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

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a[i] >> b[i];
    }
    compress();
    precalc();

    int answer = 0;
    fill(dp[0], dp[0] + M + 1, 1);
    for (int i = 1; i <= N; i++) {
        for (int x = a[i]; x <= b[i]; x++) {
            for (int j = i; j >= 1; j--) {
                if (a[j] <= x && x <= b[j]) {
                    dp[i][x] = (dp[i][x] + (ll) dp[j - 1][x - 1] * choose[x][i - j + 1]) % MOD;
                }
            }
        }
        for (int x = 1; x <= M; x++) {
            dp[i][x] += dp[i][x - 1];
            if (dp[i][x] >= MOD) {
                dp[i][x] -= MOD;
            }
        }
        answer += dp[i][b[i]];
        if (answer >= MOD) {
            answer -= MOD;
        }
        for (int x = 0; x <= M; x++) {
            dp[i][x] += dp[i - 1][x];
            if (dp[i][x] >= MOD) {
                dp[i][x] -= MOD;
            }
        }
    }
    cout << answer << "\n";

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 9292 KB Output is correct
2 Correct 633 ms 9256 KB Output is correct
3 Correct 629 ms 9284 KB Output is correct
4 Correct 620 ms 9164 KB Output is correct
5 Correct 621 ms 9408 KB Output is correct
6 Correct 613 ms 9188 KB Output is correct
7 Correct 616 ms 9224 KB Output is correct
8 Correct 606 ms 9348 KB Output is correct
9 Correct 622 ms 9184 KB Output is correct
10 Correct 618 ms 9292 KB Output is correct
11 Correct 619 ms 9248 KB Output is correct
12 Correct 613 ms 9296 KB Output is correct
13 Correct 613 ms 9300 KB Output is correct
14 Correct 619 ms 9188 KB Output is correct
15 Correct 612 ms 9228 KB Output is correct
16 Correct 112 ms 4324 KB Output is correct
17 Correct 123 ms 4356 KB Output is correct
18 Correct 118 ms 4396 KB Output is correct
19 Correct 121 ms 4384 KB Output is correct
20 Correct 118 ms 4408 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 9292 KB Output is correct
2 Correct 633 ms 9256 KB Output is correct
3 Correct 629 ms 9284 KB Output is correct
4 Correct 620 ms 9164 KB Output is correct
5 Correct 621 ms 9408 KB Output is correct
6 Correct 613 ms 9188 KB Output is correct
7 Correct 616 ms 9224 KB Output is correct
8 Correct 606 ms 9348 KB Output is correct
9 Correct 622 ms 9184 KB Output is correct
10 Correct 618 ms 9292 KB Output is correct
11 Correct 619 ms 9248 KB Output is correct
12 Correct 613 ms 9296 KB Output is correct
13 Correct 613 ms 9300 KB Output is correct
14 Correct 619 ms 9188 KB Output is correct
15 Correct 612 ms 9228 KB Output is correct
16 Correct 112 ms 4324 KB Output is correct
17 Correct 123 ms 4356 KB Output is correct
18 Correct 118 ms 4396 KB Output is correct
19 Correct 121 ms 4384 KB Output is correct
20 Correct 118 ms 4408 KB Output is correct
21 Incorrect 1129 ms 11928 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 2588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 9292 KB Output is correct
2 Correct 633 ms 9256 KB Output is correct
3 Correct 629 ms 9284 KB Output is correct
4 Correct 620 ms 9164 KB Output is correct
5 Correct 621 ms 9408 KB Output is correct
6 Correct 613 ms 9188 KB Output is correct
7 Correct 616 ms 9224 KB Output is correct
8 Correct 606 ms 9348 KB Output is correct
9 Correct 622 ms 9184 KB Output is correct
10 Correct 618 ms 9292 KB Output is correct
11 Correct 619 ms 9248 KB Output is correct
12 Correct 613 ms 9296 KB Output is correct
13 Correct 613 ms 9300 KB Output is correct
14 Correct 619 ms 9188 KB Output is correct
15 Correct 612 ms 9228 KB Output is correct
16 Correct 112 ms 4324 KB Output is correct
17 Correct 123 ms 4356 KB Output is correct
18 Correct 118 ms 4396 KB Output is correct
19 Correct 121 ms 4384 KB Output is correct
20 Correct 118 ms 4408 KB Output is correct
21 Incorrect 1129 ms 11928 KB Output isn't correct
22 Halted 0 ms 0 KB -