Submission #461045

#	Time	Username	Problem	Language	Result	Execution time	Memory
461045		TeaTime	Stove (JOI18_stove)	C++17	100 / 100	28 ms	3228 KiB

stove

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
typedef long double ld;

const ll SZ = 2e5 + 100, INF = 1e9 + 10, MX = 4e5 + 210;

struct qr {
    ll t, l, r, i;
};
vector<qr> qs;
ll n, k;

int main() {
    fastInp;

    cin >> n >> k;

    vector<ll> vec(n), srt;
    for (auto& c : vec) cin >> c;
    
    for (int i = 1; i < vec.size(); i++) {
        srt.push_back(vec[i] - vec[i - 1] - 1);
    }

    sort(srt.rbegin(), srt.rend());

    ll ans = vec.back() - vec[0] + 1;
    for (int i = 0; i < min(ll(srt.size()), k - 1); i++) {
        ans -= srt[i];
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 1; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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