제출 #1031634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031634		Phuoc	Stove (JOI18_stove)	C++14	100 / 100	16 ms	2804 KiB

stove

#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
 
/* Author: Pham Gia Phuoc */
 
const int MOD = (int)(1e9) + 7;
 
template <class T1, class T2>
    void add(T1 &a, T2 b){
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
template <class T1, class T2>
    void sub(T1 &a, T2 b){
        a -= b;
        if(a < 0) a += MOD;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if(a > b){a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if(a < b){a = b; return true;} return false;
    }
 
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
 
const int MAX = 100010;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;
 
int N, K, t[MAX];
 
void init(){
    cin >> N >> K;
    for(int i = 1; i <= N; i++) cin >> t[i];
}
 
bool checkSubtask1(){
    if(N > 20) return false;
    for(int i = 1; i <= N; i++) if(t[i] > 20) return false;
    return true;
}
 
ll solveSubtask1(){
    ll ans = INF;
    for(int mask = 0; mask < MASK(N); mask++) if(__builtin_popcount(mask) <= K - 1) {
        ll cur = 0;
        int pre = 1;
        for(int i = 2; i <= N; i++) if(BIT(mask, i - 1)) {
            cur += (t[i - 1] + 1 - t[pre]);
            pre = i;
        }
        cur += (t[N] + 1 - t[pre]);
        minimize(ans, cur);
    }
    // cout << ans << el;
    return ans;
}

ll solveSubtask3(){
    ll ans = t[N] - t[1] + 1;
    vector <ll> b;
    for(int i = 1; i < N; i++) b.push_back(1LL * (t[i + 1] - (t[i] + 1)));
    sort(b.begin(), b.end(), greater <ll>());
    // for(int i = 0; i < b.size(); i++) cout << b[i] << ' ';
    if(K > 1){
        for(int i = 0; i < K - 1; i++){
            ans -= b[i];
        }
    }   
    return ans;
}
 
void gen(){
    N = 10; K = 2;
    for(int i = 1; i <= N; i++) t[i] = rand() % 1000;
    sort(t + 1, t + N + 1);
}

void solve(){
    // if(checkSubtask1()){solveSubtask1(); return;}
    // solveSubtask3();
    // ll fi = solveSubtask1();
    // ll se = solveSubtask3();
    // // ll se;
    // if(fi != se){
    //     cout << "WA" << el;
    //     for(int i = 1; i <= N; i++) cout << t[i] << ' ';
    // }
    // else cout << "AC" << el;
    // cout << solveSubtask1() << el << solveSubtask3() << el;
    // solveSubtask3();
    // cout << el;
    cout << solveSubtask3() << el;

}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define test "test"
    srand(time(0));
    int t = 1;
    while(t--){
        // gen();
        init();
        solve();
    }
    
    return 0;
}
 
 
 
/*** ROAD TO VOI 2024 ***/

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