Submission #770489

#	Time	Username	Problem	Language	Result	Execution time	Memory
770489		sadsa	Stove (JOI18_stove)	C++17	100 / 100	45 ms	4204 KiB

stove

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using ii = tuple<int, int>;
using vii = vector<ii>;

template <typename T>
istream &operator>>(istream &in, vector<T> &vec) {
    for (auto &x : vec) in >> x;
    return in;
}

template <typename... Ts>
istream &operator>>(istream &in, tuple<Ts...> &tuple) {
    apply([&in](auto&... args) {
        ((in >> args), ...);
    }, tuple);
    return in;
}

template <typename... Ts>
auto IN() {
    tuple<Ts...> result;
    apply([](auto&... args) {
        ((cin >> args), ...);
    }, result);
    return result;
}

template <typename T>
void OUT(T&& arg) {
    cout << arg << '\n';
}

template <typename T, typename... Ts>
void OUT(T&& x, Ts&&... y) {
    cout << x << ' ';
    OUT(y...);
}

int main() {
    auto [n, k] = IN<int, int>();
    vi T(n);

    cin >> T;

    vii groups{{T[0], T[0]+1}};
    vii gaps;

    for (int i = 1; i < T.size(); ++i) {
        int Ti = T[i];
        auto &[f, t] = groups.back();
        if (t == Ti) ++t;
        else {
            gaps.emplace_back(t, Ti);
            groups.emplace_back(Ti, Ti+1);
        }
    }

    int ans = n;
    k -= groups.size();

    // sort gaps by length
    stable_sort(gaps.begin(), gaps.end(), [] (auto a, auto b) {
        return get<1>(a) - get<0>(a) < get<1>(b) - get<0>(b);
    });

    int i = 0;
    for (; k < 0; ++k) {
        int gap_size = get<1>(gaps[i]) - get<0>(gaps[i]);
        ans += gap_size;
        ++i;
    }

    OUT(ans);

	return 0;
}

Compilation message (stderr)

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

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