Submission #1259032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259032		khanhdangiuu	Boat (APIO16_boat)	C++20	9 / 100	74 ms	2116 KiB

boat

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<long long> a(N), b(N);
    vector<long long> vals;
    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i];
        vals.push_back(a[i]);
        vals.push_back(b[i]);
    }

    // nén toạ độ
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int M = vals.size();

    vector<vector<int>> dp(N, vector<int>(M, 0));

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        // prefix sum của tất cả dp[j] với j < i
        vector<int> prefix(M, 0);
        if (i > 0) {
            for (int k = 0; k < M; k++) {
                long long sum = 0;
                for (int j = 0; j < i; j++) sum += dp[j][k];
                prefix[k] = sum % MOD;
            }
            for (int k = 1; k < M; k++) {
                prefix[k] = (prefix[k] + prefix[k-1]) % MOD;
            }
        }
        // gán giá trị cho dp[i]
        for (int k = 0; k < M; k++) {
            if (vals[k] < a[i] || vals[k] > b[i]) continue;
            long long ways = 1; // khởi đầu (chỉ riêng trường này gửi)
            if (i > 0 && k > 0) ways += prefix[k-1];
            dp[i][k] = ways % MOD;
            ans = (ans + dp[i][k]) % MOD;
        }
    }

    cout << ans % MOD << "\n";
    return 0;
}

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