Submission #1125446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125446		ducanh0811	Stove (JOI18_stove)	C++20	100 / 100	92 ms	8896 KiB

stove

//
#include <bits/stdc++.h>
#define         int             long long
#define         fi              first
#define         se              second
#define         pii             pair<int,int>
#define         pb              push_back
#define         eb              emplace_back
#define         MASK(i)         (1ll << (i))
#define         FOR(i,a,b)      for (int i = (a); i <= (b); ++i)
#define         REV(i,a,b)      for (int i = (a); i >= (b); --i)
using namespace std;

int n, k;
#define MAXN 100005
int a[MAXN];

struct CMP{
    bool operator () (const pair<int,int> &a, const pair<int,int> &b){
        return a.first < b.first;
    }
};

priority_queue<pair<int,int>, vector<pair<int,int>> , CMP> pq;

multiset<pair<int,int>> ms;

void solve(){
    cin >> n >> k;
    FOR(i,1,n) cin >> a[i];
    FOR(i,2,n){
        pq.push(make_pair(a[i] - a[i - 1], i));
    }
    ms.insert(make_pair(a[1], a[n]));
    k--;
    while (k--){
        pair<int,int> top = pq.top();
        pq.pop();
        int pos = top.second;
        auto it = ms.upper_bound({a[pos], -1});
        it--;
        int ll = (*it).first;
        int rr = (*it).second;
        ms.erase(it);
        ms.insert(make_pair(a[pos], rr));
        ms.insert(make_pair(ll, a[pos - 1]));
    }
    int res = 0;
    for (const pair<int,int> &x : ms){
        res += (x.second + 1 - x.first);
    }
    cout << res;
}

#define task ""
int32_t main(){
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

stove.cpp: In function 'int32_t main()':
stove.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
stove.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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