Submission #996390

#	Time	Username	Problem	Language	Result	Execution time	Memory
996390		presko	Stove (JOI18_stove)	C++14	100 / 100	34 ms	3288 KiB

stove

#include<iostream>
#include<vector>
#include<algorithm>
#define MAXN 100010
using namespace std;
vector<pair<int,int>> order;
vector<int> indx;
int a[MAXN];
int main()
{
    int n,k;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i>1)order.push_back({a[i]-a[i-1],i});
    }
    if(k==1){cout<<a[n]+1-a[1]<<"\n";return 0;}
    if(k==n){cout<<n<<"\n";return 0;}
    sort(order.begin(),order.end());
    int cntr=0;
    long long ans=0;
    for(int i=order.size()-1;i>=0;i--)
    {
        int val=order[i].first;
        int ind=order[i].second;
        cntr++;
        indx.push_back(ind);
        if(cntr>=k-1)break;
    }
    sort(indx.begin(),indx.end());
    indx.push_back(0);
    int curr=0,last=1;
    for(int i=1;i<=n;i++)
    {
        if(i==indx[curr])
        {
            ans+=a[i-1]-a[last]+1;
            last=i;
            curr++;
        }
    }
    ans+=a[n]-a[last]+1;
    cout<<ans<<"\n";
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:27:13: warning: unused variable 'val' [-Wunused-variable]
   27 |         int val=order[i].first;
      |             ^~~

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