Submission #119791

#	Time	Username	Problem	Language	Result	Execution time	Memory
119791		Autoratch	Stove (JOI18_stove)	C++14	100 / 100	38 ms	3832 KiB

stove

#include <bits/stdc++.h>
 using namespace std;
 
 const int N = 1e5;
 
 int n,k,ans,all;
 int a[N],pa[N];
 priority_queue<pair<int,pair<int,int> > > q;
 
 int root(int x)
 {
     if(pa[x]==x) return x;
     else return pa[x] = root(pa[x]);
 }
 
 int main()
 {
     ios_base::sync_with_stdio(0); cin.tie(0);
 
     cin >> n >> k;
 
     for(int i = 0;i < n;i++) cin >> a[i],pa[i] = i;
 
     sort(a,a+n);
 
     for(int i = 0;i < n-1;i++) q.push({a[i]-a[i+1],{i,i+1}}),all+=a[i+1]-a[i];
 
     for(int i = 0;i < n-k;i++)
     {
         while(!q.empty() and root(q.top().second.first)==root(q.top().second.second)) q.pop();
         int a = q.top().second.first,b = q.top().second.second;
         ans-=q.top().first;
         pa[root(a)] = root(b);
     }
 
     cout << ans+k;
 }

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