Submission #1292980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292980		redminote13pro	Stove (JOI18_stove)	C++20	0 / 100	0 ms	332 KiB

stove

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#define McQueen ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i , a , n) for(int i = a; i < n; i++)
#define scan(a) for(auto & x : a) cin >> x;
#define rall(a) a.rbegin(), a.rend()
#define all(a) a.begin(), a.end()
#define double long double
#define int long long

using ll = long long;
using pii = pair<int , int>;
using ull = unsigned long long;

using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;

const ll mod = 1e9 + 7 , LOG = 20 , INF = 1e18 , N = 1e5 + 5 , K = 1 << 20;

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

struct SegmentTree{
	int n;
	vector<int> der;

	void build(vector<int> & a , int v , int l , int r){
		if(r - l == 1){
			if(l < (ll)a.size()) der[v] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(a , v * 2 + 1 , l , mid);
		build(a , v * 2 + 2 , mid , r);
		der[v] = der[v * 2 + 1] + der[v * 2 + 2];
	}

	SegmentTree(vector<int> & a){
		n = 1;
		while(n < (ll)a.size()) n <<= 1;
		der.assign(n * 2 - 1 , 0LL);
		build(a , 0 , 0 , n);
	};

	void update(int v , int l , int r , int i , int val){
		if(r - l == 1){
			der[v] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if(i < mid) update(v * 2 + 1 , l , mid , i , val);
		else update(v * 2 + 2 , mid , r , i , val);
		der[v] = der[v * 2 + 1] + der[v * 2 + 2];
	}
	void update(int i , int val){
		update(0 , 0 , n , i , val);
	}

	int get(int v , int l , int r , int ql , int qr){
		if(l >= qr or r <= ql) return 0LL;
		if(l >= ql and r >= qr) return der[v];
		int mid = (l + r) >> 1;
		int x = get(v * 2 + 1 , l , mid , ql , qr);
		int y = get(v * 2 + 2 , mid , r , ql , qr);
		return x + y;
	}

	int get(int ql , int qr){
		return get(0 , 0 , n , ql , qr);
	}
	
};

struct SegmentTree1 {

	int n;
	vector<int> der;

	void build(vector<int> & a , int v , int l , int r){
		if(r - l == 1){
			if(l < (ll)a.size()) der[v] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(a , v * 2 + 1 , l , mid);
		build(a , v * 2 + 2 , mid , r);
		der[v] = max(der[v * 2 + 1] , der[v * 2 + 2]);
	}

	SegmentTree1(vector<int> & a){
		n = 1;
		while(n < (ll)a.size()) n <<= 1;
		der.assign(n * 2 - 1 , -INF);
		build(a , 0 , 0 , n);
	};

	void update(int v , int l , int r , int i , int val){
		if(r - l == 1) {
			der[v] = val;
			return;
		}
		int mid = (l + r) >> 1;
		if(i < mid) update(v * 2 + 1 , l , mid , i , val);
		else update(v * 2 + 2 , mid , r , i , val);

		der[v] = max(der[v * 2 + 1] , der[v * 2 + 2]);
	}

	void update(int i , int val){
		update(0 , 0 , n , i , val);
	}
	int get(int v , int l , int r , int ql , int qr){
		if(l >= qr or r <= ql) return -INF;
		if(l >= ql and r <= qr) return der[v];
		int mid = (l + r) >> 1;
		int x = get(v * 2 + 1 , l , mid , ql , qr);
		int y = get(v * 2 + 2 , mid , r , ql , qr);
		return max(x , y);
	}
	int get(int ql , int qr) {
		return get(0 , 0 , n , ql , qr);
	}
};
inline void solve(){
	int n , k;
	cin >> n >> k;

	vector<int> a(n);
	scan(a);

	vector<int> b(n);

	for(int i = 0; i < n; i++){
		if(i > 0) b[i - 1] = a[i] - a[i - 1] - 1; 
	}
	sort(all(b));

	int ans = n;
	for(int i = 0; i < n - k; i++){
		ans += b[i];
	}
	cout << ans << "\n";
}

signed main(){
//freopen("gcm.in", "r", stdin); freopen("gcm.out", "w", stdout);
	McQueen;
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		solve();
	}
	return 0;
}

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