Submission #669793

#	Time	Username	Problem	Language	Result	Execution time	Memory
669793		Cyanmond	Autobahn (COI21_autobahn)	C++17	0 / 100	1 ms	300 KiB

autobahn

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int N, K;
    i64 X;
    std::cin >> N >> K >> X;

    std::vector<i64> L(N), T(N), R(N);
    std::vector<i64> press;
    for (int i = 0; i < N; ++i) {
        std::cin >> L[i] >> T[i] >> R[i];
        ++R[i];
        T[i] += L[i];
        T[i] = std::min(T[i], R[i]);
        press.push_back(L[i]);
        press.push_back(T[i]);
        press.push_back(R[i]);
    }
    std::sort(press.begin(), press.end());
    press.erase(std::unique(press.begin(), press.end()), press.end());

    auto calc_index = [&](const i64 x) {
        return (int)(std::lower_bound(press.begin(), press.end(), x) - press.begin());
    };

    const int M = (int)press.size();
    std::vector<i64> people(M);
    for (int i = 0; i < N; ++i) {
        ++people[calc_index(L[i])];
        --people[calc_index(R[i])];
    }
    for (int i = 1; i < M; ++i) {
        people[i] += people[i - 1];
    }

    std::vector<i64> score(M);
    for (int i = 0; i < N; ++i) {
        ++score[calc_index(T[i])];
        --score[calc_index(R[i])];
    }
    for (int i = 1; i < M; ++i) {
        score[i] += score[i - 1];
    }
    for (int i = 0; i < M; ++i) {
        if (people[i] < K) {
            score[i] = 0;
        }
    }

    std::vector<i64> score_r(M + 1);
    for (int i = 0; i < M; ++i) {
        score_r[i + 1] += score_r[i] + score[i] * (i + 1 == M ? 0 : press[i + 1] - press[i]);
    }

    auto calc_score = [&](const i64 l, const i64 r) {
        const int l_index = calc_index(l);
        const int r_index = calc_index(r);
        assert(press[l_index] == l or press[r_index] == r);
        if (press[l_index] == l) {
            i64 ret = score_r[r_index] - score_r[l_index];
            if (r_index != M) {
                ret -= score[r_index - 1] * (press[r_index] - r);
            }
            return ret;
        } else {
            i64 ret = score_r[r_index] - (l_index == 0 ? 0 : score_r[l_index - 1]);
            if (l_index != 0) {
                ret -= score[l_index - 1] * (press[l_index] - l);
            }
            return ret;
        }
    };

    i64 answer = 0;
    for (int i = 0; i < M; ++i) {
        answer = std::max(answer, calc_score(press[i], press[i] + X));
        answer = std::max(answer, calc_score(press[i] - X, press[i]));
    }

    std::cout << answer << std::endl;
}

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