oj.uz

Submission #554691

# Submission time Handle Problem Language Result Execution time Memory
554691 2022-04-29T07:43:20 Z alextodoran Boat (APIO16_boat) C++17
0 / 100
 341 ms 5232 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 * 2;

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++) {
        mp[v[i]] = ++M;
        l[M] = (i == 0 ? 1 : v[i - 1] + 1);
        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--) {
                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
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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