Submission #554696

#	Time	Username	Problem	Language	Result	Execution time	Memory
554696		alextodoran	Boat (APIO16_boat)	C++17	9 / 100	965 ms	11820 KiB

boat

/**
 ____ ____ ____ ____ ____
||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 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42