| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1162321 | SP_Caramen | Stove (JOI18_stove) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> arrival_times(n);
for (int i = 0; i < n; ++i) {
cin >> arrival_times[i];
}
sort(arrival_times.begin(), arrival_times.end());
long long min_total_time = -1;
// Function to calculate the total stove time for a given set of turn-on times
auto calculate_total_time = [&](constvector<int>&turn_on_times) {
long long total_time = 0;
int guest_index = 0;
int turn_on_index = 0;
while (guest_index < n) {
if (turn_on_index < turn_on_times.size() && arrival_times[guest_index] >= turn_on_times[turn_on_index]) {
// Stove is turned on before or at the same time as the guest arrives
total_time += (arrival_times[guest_index] + 1) - arrival_times[guest_index]; // Stove on for 1 unit of time
guest_index++;
} else {
// Find the next turn-on time that is after the guest's arrival
bool found_next = false;
for (int j = 0; j < turn_on_times.size(); ++j){
if(turn_on_times[j] > arrival_times[guest_index]){
turn_on_index = j;
found_next = true;
break;
}
}
if(found_next){
} else {
// If no more turn on available for this guest, it is an invalid arrangement, so we return a big number
return (long long)1e18;
}
}
if(turn_on_index < turn_on_times.size()){
turn_on_index++;
}
}
return total_time;
};
// Generate all possible combinations of K turn-on times
vector<int> turn_on_times(k);
function<void(int, int)> generate_combinations =
[&](intindex,intstart) {
if (index == k) {
// Sort the turn-on times
sort(turn_on_times.begin(), turn_on_times.end());
// Calculate the total stove time for this combination
long long current_total_time = calculate_total_time(turn_on_times);
// Update the minimum total time
if (min_total_time == -1 || current_total_time < min_total_time) {
min_total_time = current_total_time;
}
return;
}
for (int i = start; i <= arrival_times[n-1]; ++i) {
turn_on_times[index] = i;
generate_combinations(index + 1, i);
}
};
// Start generating combinations from time 0
if(k > 0){
generate_combinations(0, 0);
} else {
min_total_time = (long long)1e18;
}
// If K is 0, check if any guest visits
if (k == 0){
bool any_guest = false;
for (int i = 0; i < n; i++){
any_guest = true;
break;
}
if (any_guest) {
cout << (long long)1e18 << endl;
return 0;
} else {
cout << 0 << endl;
return 0;
}
}
if(min_total_time == (long long)1e18){
// If no K diêm can serve all guests, consider serving each guest
min_total_time = n;
if (k < 1){
min_total_time = (long long)1e18;
}
}
cout << min_total_time << endl;
return 0;
}