Submission #696673

#	Time	Username	Problem	Language	Result	Execution time	Memory
696673		TranGiaHuy1508	Parkovi (COCI22_parkovi)	C++17	30 / 110	134 ms	9272 KiB

Main

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

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long

int n, k;
vector<int> Ws;
vector<int> lst;

bool check(int threshold){
	lst.clear();

	int prev = -(int)1e16, wait = (int)1e16;
	int crr = 0;
	for (int i = 0; i < n; i++){
		if (crr - prev > threshold){
			wait = min(wait, crr);
			if (i < n-1){
				int newcrr = crr + Ws[i];
				if (newcrr - wait > threshold){
					lst.push_back(i);
					prev = crr;
					wait = (int)1e16;
				}
			}
		}
		if (i < n-1) crr += Ws[i];
	}
	if (wait < (int)1e16) lst.push_back(n-1);

	return (int)lst.size() <= k;
}

void main_program(){
	// Sub 3

	cin >> n >> k;
	Ws.resize(n-1);
	for (int i = 0; i < n-1; i++){
		int x, y, w; cin >> x >> y >> w;
		Ws[i] = w;
	}

	int l = 0, r = 1e15;
	while (l < r){
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	check(l);
	cout << l << "\n";
	vector<int> mark(n);
	for (auto i: lst){
		mark[i] = 1; k--;
	}
	for (int i = 0; i < n; i++){
		if (!mark[i] && k){
			mark[i] = 1; k--;
		}
	}
	for (int i = 0; i < n; i++){
		if (mark[i]) cout << i+1 << " ";
	}
	cout << "\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 30 / 30
• Subtask 4: 0 / 60