oj.uz

Submission #696669

# Submission time Handle Problem Language Result Execution time Memory
696669 2023-02-07T03:28:24 Z TranGiaHuy1508 Parkovi (COCI22_parkovi) C++17
0 / 110
 113 ms 8700 KB 
#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 = -1e16, wait = 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 = 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";
	for (auto i: lst) cout << i+1 << " ";
	cout << "\n";
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2056 KB Output is correct
2 Correct 76 ms 2248 KB Output is correct
3 Incorrect 83 ms 2276 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6220 KB Output is correct
2 Correct 79 ms 6024 KB Output is correct
3 Correct 69 ms 5708 KB Output is correct
4 Correct 69 ms 5688 KB Output is correct
5 Correct 97 ms 8700 KB Output is correct
6 Correct 104 ms 7524 KB Output is correct
7 Correct 113 ms 8392 KB Output is correct
8 Correct 70 ms 5560 KB Output is correct
9 Correct 70 ms 5452 KB Output is correct
10 Correct 73 ms 5460 KB Output is correct
11 Correct 67 ms 5220 KB Output is correct
12 Incorrect 104 ms 8304 KB Unexpected end of file - int32 expected
13 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -