oj.uz

Submission #633505

# Submission time Handle Problem Language Result Execution time Memory
633505 2022-08-22T15:28:38 Z ngano_upat_na Stove (JOI18_stove) C++17
0 / 100
 1 ms 256 KB 
#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<int> 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++) {
        int 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<int,int>> 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];
    }   
    cout << ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 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 1 ms 256 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 1 ms 256 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -