Submission #636933

#	Time	Username	Problem	Language	Result	Execution time	Memory
636933		birthdaycake	Stove (JOI18_stove)	C++17	100 / 100	96 ms	8364 KiB

stove

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;


int a[200001];
 
 
signed main(){
    
    int n,k, ans = 0; cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a,a+n);
    vector<pair<int,int>>d; 
    set<int>x;
    for(int i = 0; i < n - 1; i++){
        d.push_back({a[i + 1] - a[i], i});
    }
    sort(d.begin(), d.end());
    reverse(d.begin(), d.end());
    for(int i = 0; i < k - 1; i++){
        x.insert(d[i].second);
    }
    int beg = INT_MAX, ed = 0;
    for(int i = 0; i < n; i++){
        beg = min(beg,a[i]);
        ed = max(ed,a[i]);
        if(x.count(i)){
            ans += (ed - beg + 1);
            beg = INT_MAX; ed = 0;
        }
    }
    ans += (ed - beg + 1);
    cout << ans;
    return 0;
}

Compilation message (stderr)

stove.cpp:13: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   13 | #pragma GCC optimization ("O3")
      | 
stove.cpp:14: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   14 | #pragma GCC optimization ("unroll-loops")
      |

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