제출 #1323981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323981		sh_qaxxorov_571	Stove (JOI18_stove)	C++20	100 / 100	15 ms	2360 KiB

stove

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * JOI-kun pechka masalasi yechimi.
 * Vaqt murakkabligi: O(N log N) - saralash tufayli.
 * Xotira murakkabligi: O(N).
 */

int main() {
    // Tezkor kiritish-chiqarish
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> T(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i];
    }

    // Umumiy ishlash vaqti boshida: birinchi mehmon kelishidan oxirgisigacha
    long long total_time = (T[N - 1] + 1) - T[0];

    // Mehmonlar orasidagi bo'shliqlarni hisoblaymiz
    vector<long long> gaps;
    for (int i = 0; i < N - 1; i++) {
        long long gap = T[i + 1] - (T[i] + 1);
        if (gap > 0) {
            gaps.push_back(gap);
        }
    }

    // Bo'shliqlarni kattaligiga ko'ra tartiblaymiz (kamayish tartibida)
    sort(gaps.rbegin(), gaps.rend());

    // K-1 ta eng katta bo'shliqni umumiy vaqtdan ayiramiz
    // Chunki bizda pechkani K marta yoqish imkoni bor
    for (int i = 0; i < min((int)gaps.size(), K - 1); i++) {
        total_time -= gaps[i];
    }

    cout << total_time << endl;

    return 0;
}

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