Submission #1255057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255057		kunzaZa183	Boat (APIO16_boat)	C++20	0 / 100	2 ms	324 KiB

boat

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

const ll MOD = 1'000'000'007;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> range(n);
    set<int> all_values;

    // Read input and collect all possible boat values
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b};
        all_values.insert(a);
        all_values.insert(b);
    }

    // Optional: if ranges are small enough (like in subtasks), include full ranges
    // Otherwise just store a and b and assume ranges will be reconstructed later

    // Coordinate compression
    vector<int> vals(all_values.begin(), all_values.end());
    unordered_map<int, int> val_to_index;
    int m = vals.size();
    for (int i = 0; i < m; ++i) {
        val_to_index[vals[i]] = i;
    }

    // dp[i]: number of ways to form a valid sequence ending in boat value vals[i]
    vector<ll> dp(m, 0);

    // For the first school
    for (int i = 0; i < m; ++i) {
        int x = vals[i];
        if (x >= range[0].first && x <= range[0].second) {
            dp[i] = 1;
        }
    }

    for (int school = 1; school < n; ++school) {
        // Build prefix sum over previous dp
        vector<ll> prefix(m + 1, 0);
        for (int i = 0; i < m; ++i) {
            prefix[i + 1] = (prefix[i] + dp[i]) % MOD;
        }

        vector<ll> new_dp(m, 0);
        for (int i = 0; i < m; ++i) {
            int x = vals[i];
            if (x >= range[school].first && x <= range[school].second) {
                // Valid values are strictly greater than previous values
                new_dp[i] = prefix[i]; // sum of all dp[j] where j < i
            }
        }

        // Also allow school to skip sending boats — keep previous dp values
        for (int i = 0; i < m; ++i) {
            new_dp[i] = (new_dp[i] + dp[i]) % MOD;
        }

        dp = new_dp;
    }

    // Answer: sum over all dp[i], but must have used at least one boat
    ll ans = 0;
    for (ll x : dp) {
        ans = (ans + x) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

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