Submission #1130651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130651		OI_Account	Boat (APIO16_boat)	C++20	9 / 100	664 ms	12452 KiB

boat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 500;
const int X = 1000;
const ll MOD = 1'000'000'007;

int n, a[N + 10], b[N + 10];
int l[N + 10], r[N + 10], x;
ll c[X + 10][N + 10], dp[2][X + 10][N + 10];
ll fact[N + 10], invFact[N + 10], len[X + 10];
vector<ll> vec;

void readInput() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        vec.push_back(a[i]);
        vec.push_back(b[i] + 1);
    }
}

void cmp() {
    sort(vec.begin(), vec.end());
    vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
    for (int i = 1; i <= n; i++) {
        l[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
        r[i] = lower_bound(vec.begin(), vec.end(), b[i] + 1) - vec.begin();
    }
    for (int i = 0; i + 1 < vec.size(); i++)
        len[i] = vec[i + 1] - vec[i];
    x = (int) vec.size() - 2;
}

ll power(ll x, ll k) {
    return k? power(x * x % MOD, k >> 1) * ((k & 1)? x: 1) % MOD: 1;
}

void calcFact() {
    fact[0] = invFact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        invFact[i] = power(fact[i], MOD - 2);
    }
}

void calcC() {
    for (int i = 0; i <= x; i++) {
        ll mul = 1;
        for (int j = 0; j <= n; j++) {
            c[i][j] = mul * invFact[j] % MOD;
            mul = mul * (len[i] - j) % MOD;
        }
    }
}

void clearDP(int t) {
    for (int i = 0; i <= x; i++)
        for (int j = 0; j <= n; j++)
            dp[t][i][j] = 0;
}

void calcDP() {
    for (int k = 1; k <= n; k++) {
        int last = 1 - k % 2, tmp = k % 2;
        clearDP(tmp);
        ll sum = 0;
        for (int i = 0; i <= x; i++) {
            if (l[k] <= i && i < r[k]) {
                dp[tmp][i][1] = (sum + 1) % MOD;
                for (int j = 1; j < k; j++)
                    dp[tmp][i][j + 1] = (dp[tmp][i][j + 1] + dp[last][i][j]) % MOD;
            }
            for (int j = 1; j < k; j++) {
                sum = (sum + dp[last][i][j] * (c[i][j] * fact[j] % MOD)) % MOD;
                dp[tmp][i][j] = (dp[tmp][i][j] + dp[last][i][j]) % MOD;
            }
        }
    }
}

void calcAns() {
    int t = n % 2;
    ll ans = 0;
    for (int i = 0; i <= x; i++)
        for (int j = 1; j <= n; j++)
            ans = (ans + dp[t][i][j] * (c[i][j] * fact[j] % MOD)) % MOD;
    cout << ans << flush;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    cmp();
    calcFact();
    calcC();
    calcDP();
    calcAns();
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42