Submission #963946

#	Time	Username	Problem	Language	Result	Execution time	Memory
963946		Mardonbekhazratov	Stove (JOI18_stove)	C++17	100 / 100	18 ms	2516 KiB

stove

/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,sse4a,popcnt,abm,mmx,avx,avx2")
*/
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
 
#define ll long long
// #define int ll
#define fast cin.tie(0)->sync_with_stdio(0),cout.tie(0)
#define ff first
#define ss second
#define pi pair<int,int>
#define vi vector<int>
#define mi map<int,int>
#define mll map<ll,ll>
#define vll vector<ll>
#define vvi vector<vi>
#define vpi vector<pi>
#define vvll vector<vll>
#define pb push_back
#define p_b pop_back
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"
#define NO cout<<"NO"
#define print(a,l,r) for(int qwert=l;qwert<r;qwert++)cout<<a[qwert]<<' '
#define input(a,l,r) for(int qwert=l;qwert<r;qwert++)cin>>a[qwert]
 
 
 
const int M=1e9+7;
const int MOD=998244353;
//const int N=1e6;
const int INF=1e9;
const ll INFLL=2e18;
 
/*
#define LOCAL
#define TESTCASES
*/

#define int ll

void solve(int test_id){
    int n,k;
    cin>>n>>k;
    int last;
    cin>>last;
    vector<int>d;
    int ans=n;
    for(int i=1;i<n;i++){
        int x;
        cin>>x;
        d.pb(x-last-1);
        last=x;
    }
    sort(all(d));
    for(int i=0;i<n-k;i++) ans+=d[i];
    cout<<ans;
}

signed main(){

    fast;
 
 
    #ifdef LOCAL
        auto start = chrono::high_resolution_clock::now();
        
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        freopen("error.txt","w",stderr);
    #endif
    
    int T=1;
    
 
    #ifdef TESTCASES
        cin>>T;
    #endif
 
    for(int tests=0;tests<T;tests++){
        solve(tests);
        //cout<<(solve()?"YES":"NO");
        cout<<'\n';
    }
 
    #ifdef LOCAL
        auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
	
	    cerr << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
 
    return 0;
}

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