Submission #875131

#	Time	Username	Problem	Language	Result	Execution time	Memory
875131		misu2005	Stove (JOI18_stove)	C++11	100 / 100	73 ms	4592 KiB

stove

#include <iostream>
#include <map>

using namespace std;

int n, k, v[100002];
map<int, int> fr1, fr2;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
        if (i >= 2) {
            fr1[-v[i] + v[i-1]]++;
        }
    }

    k--;
    for (auto it:fr1) {
        if (!k)
            break;
        if (it.first == -1)
            continue;
        fr2[it.first] += min(it.second, k);
        k -= min(it.second, k);
    }

    int timp = 1;
    for (int i = 2; i <= n; i++) {
        if (v[i] - v[i-1] == 1)
            timp++;
        else {
            if (fr2[-v[i]+v[i-1]] == 0) {
                timp += v[i] - v[i-1];
            }
            else {
                fr2[v[i-1]-v[i]]--;
                timp++;
            }
        }
    }
    cout << timp;

    return 0;
}

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