Submission #226507

#	Time	Username	Problem	Language	Result	Execution time	Memory
226507		Toirov_Sadi	Stove (JOI18_stove)	C++17	100 / 100	128 ms	8052 KiB

stove

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

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()
{
    scanf("%d %d ", &n, &k);
    for(int i = 1; i <= n; i ++){
        scanf(" %d", a + i);
        s.insert({i, i});
    }
    if(n == 1){
        printf("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.rbegin(), b.rend());
    while(s.size() > k && !b.empty()){
        auto y = s.lower_bound({b.back().second.second, b.back().second.second});
        b.pop_back();
        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);
    }
    printf("%I64d", res);
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(s.size() > k && !b.empty()){
           ~~~~~~~~~^~~
stove.cpp:48:24: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     printf("%I64d", res);
                        ^
stove.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d ", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~
stove.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %d", a + i);
         ~~~~~^~~~~~~~~~~~~~

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