Submission #527758

#	Time	Username	Problem	Language	Result	Execution time	Memory
527758		KoD	Autobahn (COI21_autobahn)	C++17	50 / 100	115 ms	7824 KiB

autobahn

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

int lowb(const std::vector<int>& v, const int x) {
    return std::lower_bound(v.begin(), v.end(), x) - v.begin();
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, K, X;
    std::cin >> N >> K >> X;
    vector<int> L(N), T(N), R(N), cx;
    for (int i = 0; i < N; ++i) {
        std::cin >> L[i] >> T[i] >> R[i];
        R[i] += 1;
        cx.push_back(L[i]);
        cx.push_back(L[i] + T[i]);
        cx.push_back(R[i]);
    }
    std::sort(cx.begin(), cx.end());
    cx.erase(std::unique(cx.begin(), cx.end()), cx.end());
    const int n = cx.size();
    vector<int> exist(n), coeff(n);
    for (int i = 0; i < N; ++i) {
        exist[std::lower_bound(cx.begin(), cx.end(), L[i]) - cx.begin()] += 1;
        exist[std::lower_bound(cx.begin(), cx.end(), R[i]) - cx.begin()] -= 1;
        if (L[i] + T[i] < R[i]) {
            coeff[std::lower_bound(cx.begin(), cx.end(), L[i] + T[i]) - cx.begin()] += 1;
            coeff[std::lower_bound(cx.begin(), cx.end(), R[i]) - cx.begin()] -= 1;
        }
    }
    for (int i = 1; i < n; ++i) {
        exist[i] += exist[i - 1];
        coeff[i] += coeff[i - 1];
    }
    for (int i = 0; i < n; ++i) {
        if (exist[i] < K) {
            coeff[i] = 0;
        }
    }
    long long sum = 0, ans = 0;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j + 1 < n and cx[j + 1] - cx[i] <= X) {
            sum += (cx[j + 1] - cx[j]) * coeff[j];
            j += 1;
        }
        ans = std::max(ans, sum + coeff[j] * (X - (cx[j] - cx[i])));
        if (i == j) {
            j += 1;
        } else {
            sum -= (cx[i + 1] - cx[i]) * coeff[i];
        }
    }
    for (int i = n - 1, j = n - 1; i >= 0; --i) {
        while (j > 0 and cx[i] - cx[j - 1] <= X) {
            sum += (cx[j] - cx[j - 1]) * coeff[j - 1];
            j -= 1;
        }
        ans = std::max(ans, sum + (j == 0 ? 0 : coeff[j - 1]) * (X - (cx[i] - cx[j])));
        if (i == j) {
            j -= 1;
        } else {
            sum -= (cx[i] - cx[i - 1]) * coeff[i - 1];
        }
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50