제출 #636284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636284		PanTkd	Stove (JOI18_stove)	C++14	100 / 100	24 ms	2316 KiB

stove

//
//  main.cpp
//
//  Created by Panagiotis Chadjicostas on
//  Copyright © Panagiotis Hadjicostas. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

typedef int ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
#ifdef px
    #define p(x) cerr<<#x<<' '<<x<<endl;
#else
    #define p(x) {}
#endif
#define F first
#define S second
#define sz size
#define ls s,m,idx<<1
#define rs m+1,e,idx<<1|1
const ll MOD=ll(1e9)+7;
const ll MAXN=2*ll(1e6);
///////////////////////////////////////////////////////////////////////
void solve(){
    ll n,k;cin>>n>>k;
    vector<ll> a(n+1,ll());
    for(ll i=1;i<=n;i++)cin>>a[i];

    // logika fasi dp[i][x], eimai ston i kai xrisimopoio x stove

    // dp [i] [x] = dp [i-1] [x-1] + 1
    // dp [i] [x] = dp [i-1] [x] + a[i] - a[i-1] + 1;

    // memory :?
    /*
    ll dp [n+2][k+2];

    for(ll i=0;i<n+2;i++){
        for(ll j=0;j<k+2;j++){
            dp[i][j]=MOD;
        }
    }
    dp[1][1]=1;
    for(ll i=2;i<=n;i++){
        for(ll x=1;x<=k;x++){
            dp[i][x] = dp[i-1][x-1] + 1;
            dp[i][x]=min(dp[i][x],dp[i-1][x]+a[i]-a[i-1]);
        }
    } 
    cout<<dp[n][k]<<endl;

    */

    // pairno k mona tous + (n-k) mik diafores

    ll ans=k;
    priority_queue<ll,vi,greater<ll> > pq;
    for(ll i=2;i<=n;i++){
        pq.push(a[i]-a[i-1]);
    } 

    for(ll i=1;i<=n-k;i++){
        ans+=pq.top();
        pq.pop();
    }
    cout<<ans<<endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;//cin>>t;
    while (t--) {
        solve();
    }
    return 0;
}

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