Submission #627135

#	Time	Username	Problem	Language	Result	Execution time	Memory
627135		boris_mihov	Stove (JOI18_stove)	C++17	100 / 100	22 ms	1680 KiB

stove

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 17;
const int INF  = 2e9;

int a[MAXN], n, k;
void solve()
{
    int diff = a[n] - a[1] + 1;
    for (int i = n ; i >= 2 ; --i)
    {
        a[i] -= a[i-1];
        a[i]--;
    }

    int sum = 0;
    std::sort(a+2, a+1+n); --k;
    for (int i = n ; i >= n - k + 1 ; --i)
    {
        sum += a[i];
    }

    std::cout << diff - sum << '\n';
}

void read()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

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