Submission #718737

#	Time	Username	Problem	Language	Result	Execution time	Memory
718737		ACtor	Stove (JOI18_stove)	C++17	100 / 100	50 ms	1332 KiB

stove

#include <iostream>
#include <vector>
#include <iomanip> 
//#include <chrono>
#include <map>
#include <string>
#include <set>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>

using namespace std;
//using namespace chrono;
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define F first
#define S second
typedef long long ll;
typedef vector< int > vi;
typedef vector< ll > V;
typedef map<int, int > mp;
#define debug cout << -1 << endl;
#define REP(i, a, b) for(int i=a; i<b; i++)
#define f0r(i, n) for (int i = 0; i < n; ++i)
#define fore(a, x) for (auto& a : x)
#define fori(i, a, b) for (int i = (a); i < (b); ++i)
//#define pop pop_back
#define sz(a) (int)a.size()
//#define fin cin
//#define fout cout
const ll MOD = 1000000007;
const int INF = (int)1e9;
int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dy[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const double PI = acos(-1.0);
const double diff = 1e-6;

void solve()
{
    int n, k;
    cin >> n >> k;
    vi v(n), v2;
    ll ans;
    f0r(i, n) {
        cin >> v[i];
        if(i) v2.pb(v[i]-(v[i-1]+1));
    }
    ans = v[n-1]+1-(v[0]);
    sort(v2.begin(), v2.end());
    reverse(v2.begin(), v2.end());
    for(int i=0; i<k-1; i++) {
        ans -= v2[i];
    }
    cout << ans << "\n";
}

int main()
{
    //FastIO;
    //freopen("maxcross.in", "r", stdin);
    //freopen("maxcross.out", "w", stdout);
    //ofstream fout ("wormhole.out");
    //ifstream fin ("wormhole.in");
    int t;
    t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
}

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