Submission #657810

#	Time	Username	Problem	Language	Result	Execution time	Memory
657810		OgradL	Stove (JOI18_stove)	C++14	100 / 100	48 ms	3520 KiB

stove

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

using namespace std;

#define ll long long
#define p pair<int, int>
#define mkp make_pair
#define pb push_back

int main() {
    
    int N, K;
    cin >> N >> K;
    
    vector<ll> T(N);
    for (ll &n: T) cin >> n;
    
    vector<p> R;
    //vector<int> siz;
    int start = T[0];
    for (int i = 0; i < N; i++){
        if (i == N - 1){
            R.pb(mkp(start, T[i]+1));
            //cout << start << " " << T[i]+1 << "\n";
        } else if (T[i] + 1 != T[i + 1]){
            R.pb(mkp(start, T[i]+1));
            //siz.pb(T[i]+1 - start);
            //cout << start << " " << T[i]+1 << "\n";
            start = T[i + 1];
        }
    }
    //cout << "\n\n\n";
    
    vector<int> siz;
    for (int i = 0; i < R.size() - 1; i++){
        siz.pb(R[i+1].first - R[i].second);
        //cout << R[i].second << " " << R[i+1].first << " " << R[i+1].first - R[i].second << "\n";
    }
    
    
    sort(siz.begin(), siz.end(), greater<int>());
    
    ll sum = 0;
    for (int i = 0; i < K - 1 && i < siz.size(); i++){
        sum += siz[i];
        //cout << siz[i] << "\n";
    }
    //cout << T[N-1] << " " << T[0] << " " << sum << "\n";
    cout << T[N-1]+1-T[0]-sum << "\n";
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < R.size() - 1; i++){
      |                     ~~^~~~~~~~~~~~~~
stove.cpp:46:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < K - 1 && i < siz.size(); i++){
      |                                  ~~^~~~~~~~~~~~

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