Submission #633513

#	Time	Username	Problem	Language	Result	Execution time	Memory
633513		ngano_upat_na	Stove (JOI18_stove)	C++17	0 / 100	0 ms	212 KiB

stove

#include "bits/stdc++.h"
using namespace std;
using ll = long long;    

struct s {
    int dif;
    int l;
    int r;
};    

bool comp(s a, s b) {
    if (a.dif == b.dif) {
        return a.l < b.l;
    }   
    return a.dif > b.dif;
}   

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<ll> v(n);
    for (auto &e:v) cin >> e;
    vector<s> vs;
    
    if (n == 1) {
        cout << 1;
        return 0;
    }   
    if (k == 1) {
        cout << v[n-1] + 1 - v[0];
        return 0;
    }   
    
    for (int i=0; i<n - 1; i++) {
        ll DIF = v[i+1] - v[i], L = i, R = i+1;
        vs.push_back({DIF,L,R});
    }   
    sort(vs.begin(),vs.end(),comp);
    
    vector<pair<ll,ll>> vp;
    for (int i=0; i<k-1; i++) {
        int fi = vs[i].l, se = vs[i].r;
        vp.push_back({fi,se});
    }   
    sort(vp.begin(),vp.end());
    
    ll ans = 0;
    int cur = 0;
    for (int i=0; i<k-1; i++) {
        ll rh = v[vp[i].first] + 1;
        ans += (rh - cur);
        cur = v[vp[i].second];
    }      
    ans += (v[n - 1] - cur);
    cout << ans;
    return 0;
}   

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:39:23: warning: narrowing conversion of 'DIF' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   39 |         vs.push_back({DIF,L,R});
      |                       ^~~
stove.cpp:39:27: warning: narrowing conversion of 'L' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   39 |         vs.push_back({DIF,L,R});
      |                           ^
stove.cpp:39:29: warning: narrowing conversion of 'R' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   39 |         vs.push_back({DIF,L,R});
      |                             ^

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