oj.uz

Submission #554696

# Submission time Handle Problem Language Result Execution time Memory
554696 2022-04-29T07:58:17 Z alextodoran Boat (APIO16_boat) C++17
9 / 100
 965 ms 11820 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 && a[j] <= x && x <= b[j]; 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 649 ms 9180 KB Output is correct
2 Correct 657 ms 9220 KB Output is correct
3 Correct 640 ms 9124 KB Output is correct
4 Correct 630 ms 9104 KB Output is correct
5 Correct 649 ms 9252 KB Output is correct
6 Correct 647 ms 9140 KB Output is correct
7 Correct 681 ms 9172 KB Output is correct
8 Correct 647 ms 9324 KB Output is correct
9 Correct 622 ms 9148 KB Output is correct
10 Correct 669 ms 9152 KB Output is correct
11 Correct 661 ms 9216 KB Output is correct
12 Correct 636 ms 9140 KB Output is correct
13 Correct 665 ms 9216 KB Output is correct
14 Correct 667 ms 9120 KB Output is correct
15 Correct 669 ms 9128 KB Output is correct
16 Correct 113 ms 4344 KB Output is correct
17 Correct 126 ms 4456 KB Output is correct
18 Correct 117 ms 4424 KB Output is correct
19 Correct 138 ms 4520 KB Output is correct
20 Correct 118 ms 4364 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 9180 KB Output is correct
2 Correct 657 ms 9220 KB Output is correct
3 Correct 640 ms 9124 KB Output is correct
4 Correct 630 ms 9104 KB Output is correct
5 Correct 649 ms 9252 KB Output is correct
6 Correct 647 ms 9140 KB Output is correct
7 Correct 681 ms 9172 KB Output is correct
8 Correct 647 ms 9324 KB Output is correct
9 Correct 622 ms 9148 KB Output is correct
10 Correct 669 ms 9152 KB Output is correct
11 Correct 661 ms 9216 KB Output is correct
12 Correct 636 ms 9140 KB Output is correct
13 Correct 665 ms 9216 KB Output is correct
14 Correct 667 ms 9120 KB Output is correct
15 Correct 669 ms 9128 KB Output is correct
16 Correct 113 ms 4344 KB Output is correct
17 Correct 126 ms 4456 KB Output is correct
18 Correct 117 ms 4424 KB Output is correct
19 Correct 138 ms 4520 KB Output is correct
20 Correct 118 ms 4364 KB Output is correct
21 Incorrect 965 ms 11820 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 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 9180 KB Output is correct
2 Correct 657 ms 9220 KB Output is correct
3 Correct 640 ms 9124 KB Output is correct
4 Correct 630 ms 9104 KB Output is correct
5 Correct 649 ms 9252 KB Output is correct
6 Correct 647 ms 9140 KB Output is correct
7 Correct 681 ms 9172 KB Output is correct
8 Correct 647 ms 9324 KB Output is correct
9 Correct 622 ms 9148 KB Output is correct
10 Correct 669 ms 9152 KB Output is correct
11 Correct 661 ms 9216 KB Output is correct
12 Correct 636 ms 9140 KB Output is correct
13 Correct 665 ms 9216 KB Output is correct
14 Correct 667 ms 9120 KB Output is correct
15 Correct 669 ms 9128 KB Output is correct
16 Correct 113 ms 4344 KB Output is correct
17 Correct 126 ms 4456 KB Output is correct
18 Correct 117 ms 4424 KB Output is correct
19 Correct 138 ms 4520 KB Output is correct
20 Correct 118 ms 4364 KB Output is correct
21 Incorrect 965 ms 11820 KB Output isn't correct
22 Halted 0 ms 0 KB -