제출 #1161257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161257		Aza	Stove (JOI18_stove)	C++20	0 / 100	0 ms	324 KiB

stove

//AzaLE (Azamat Alisherov)	
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast,unroll-loops")
#define size(x) (int)x.size()
#define int long long
//#define endl '\n'
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F first
#define S second
template<class T> using oset = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;
const int MOD = 1e9 + 7;// 119 * (1 << 23) + 1;
int binpow (int a, int n){
	int res = 1;
	while (n){
		if (n & 1){
			res = (res * a) % MOD;
		}
		a = (a * a) % MOD;
		n >>= 1;
	}
	return res % MOD;
}
vector <int> v;
int n, k;
int check(int x){
	int l = 0;
	int ret = 0;
	int curcord = v[l];
	int cnt = 0;
	for(int r = 0; r < n; r++){
		if(v[r + 1] - curcord + 1 > x){
			ret += v[r] - curcord + 1;
			curcord = v[r + 1];
			cnt++;
		}
	}
	return (cnt <= k ? ret : -1);
}
void chomp(){
	cin >> n >> k;
	if(n == 1){
		cout << 1;
		return;
	}
	v.resize(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}
	v.push_back(1e18);
	int l = 0, r = 1e10;
	int ans = 1e10;
	while(l <= r){
		int mid = (l + r) / 2;
		int res = check(mid);
		//cout << mid << " " << res << endl;
		if(res != -1){
			ans = min(ans, res);
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	cout << ans;
}
signed main(){
	//ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int tasks = 1;
	//cin >> tasks;
	while(tasks--){
		chomp();
	}
}
/*

*/

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