oj.uz

Submission #633514

# Submission time Handle Problem Language Result Execution time Memory
633514 2022-08-22T16:02:18 Z ngano_upat_na Stove (JOI18_stove) C++17
0 / 100
 0 ms 212 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;    

struct s {
    ll dif;
    ll l;
    ll 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;
    for (int i=0; i<n; i++) {
        v[i] -= (v[0] - 1);
    }   
    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++) {
        ll fi = vs[i].l, se = vs[i].r;
        vp.push_back({fi,se});
    }   
    sort(vp.begin(),vp.end());
    
    ll ans = 0;
    ll 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;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -