Submission #1229777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229777		ming2900	Stove (JOI18_stove)	C++20	100 / 100	15 ms	2496 KiB

stove

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
    int N, K;
    cin >> N >> K;
    vector<int> T(N);
    for (int i = 0; i < N; ++i) {
        cin >> T[i];
    }
    sort(T.begin(), T.end());

    vector<pair<int, int>> intervals;
    int start = T[0];
    int end = T[0] + 1;

    for (int i = 1; i < N; ++i) {
        if (T[i] == end) {
            ++end;
        } else {
            intervals.push_back({start, end});
            start = T[i];
            end = T[i] + 1;
        }
    }
    intervals.push_back({start, end});
    int m = intervals.size();
    if (m <= K) {
        int total = 0;
        for (auto [s, e] : intervals) {
            total += (e - s);
        }
        cout << total << endl;
        return 0;
    }
    vector<int> gaps;
    for (int i = 0; i < m - 1; ++i) {
        int gap = intervals[i + 1].first - intervals[i].second;
        gaps.push_back(gap);
    }
    sort(gaps.begin(), gaps.end());

    int totalTime = 0;
    for (auto [s, e] : intervals) {
        totalTime += (e - s);
    }
    for (int i = 0; i < m - K; ++i) {
        totalTime += gaps[i];
    }
    cout << totalTime << endl;
    return 0;
}

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