oj.uz

Submission #633513

# Submission time Handle Problem Language Result Execution time Memory
633513 2022-08-22T15:51:34 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 {
    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

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.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 -