Submission #226499

#	Time	Username	Problem	Language	Result	Execution time	Memory
226499		Toirov_Sadi	Stove (JOI18_stove)	C++17	50 / 100	1090 ms	8048 KiB

stove

#include <bits/stdc++.h>

#define FILE
#define fr first
#define se second

using namespace std;

const long long N = 1e5 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

int n;
int k;
int a[N];
set<pair<int, int>> s;
vector<pair<int, pair<int, int>>> b;
int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        s.insert({i, i});
    }
    if(n == 1){
        cout << "1\n";
        return 0;
    }
    for(int i = 2; i <= n; i ++){
        b.push_back({a[i] - a[i - 1] + 1, {i - 1, i}});
    }
    sort(b.begin(), b.end());
    while(s.size() > k && !b.empty()){
        int l = b.begin()->second.first;
        int r = b.begin()->second.second;
        b.erase(b.begin());
        auto y = s.lower_bound({r, r});
        auto x = y;
        x --;
        if(x == s.end() || y == s.end()){
            continue;
        }
        s.erase(x);
        s.erase(y);
        s.insert({x->first, y->second});
    }
    long long res = 0;
    for(auto x: s){
        res += (a[x.second] - a[x.first] + 1);
    }
    cout << res << "\n";
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(s.size() > k && !b.empty()){
           ~~~~~~~~~^~~
stove.cpp:36:13: warning: unused variable 'l' [-Wunused-variable]
         int l = b.begin()->second.first;
             ^

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