제출 #1196534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196534		amanthaband	Stove (JOI18_stove)	C++20	50 / 100	1095 ms	11760 KiB

stove

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<vector<int>> arr;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back({x, x + 1});
    }

    
    sort(arr.begin(), arr.end());
    vector<vector<int>> ans;

    for (int i = 0; i < n; i++) {
        if (ans.empty() || arr[i][0] > ans.back()[1]) {
            ans.push_back(arr[i]);
        } else {
            ans.back()[1] = max(ans.back()[1], arr[i][1]);
        }
    }

    
    while (ans.size() > k) {
        int mn = INT_MAX;
        int idx = -1;

        
        for (int i = 0; i < (int)ans.size() - 1; i++) {
            int gap = ans[i + 1][0] - ans[i][1];
            if (gap < mn) {
                mn = gap;
                idx = i;
            }
        }

       
        vector<int> merged = {
            min(ans[idx][0], ans[idx + 1][0]),
            max(ans[idx][1], ans[idx + 1][1])
        };

        
        ans.erase(ans.begin() + idx);       
        ans.erase(ans.begin() + idx);       
        ans.insert(ans.begin() + idx, merged);
    }

    // Print result
    int total = 0;
    for (auto& v : ans) {
        total += v[1] - v[0];
    }

    cout << total << endl;


    return 0;
}

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