int solve(int N, int days, vector<int>& weights) {
int start_cap = 1;
int end_cap = 0;
for (int cargo_w : weights) {
start_cap = max(start_cap, cargo_w);
end_cap += cargo_w;
}
end_cap *= 2;
int min_required_capacity = end_cap;
while (start_cap <= end_cap) {
int mid_cap = start_cap + (end_cap - start_cap) / 2;
int active_day = 1;
int loaded_weight = 0;
int pkg_idx = 0;
bool fits_in_time = true;
while (pkg_idx < N) {
if (active_day > days) {
fits_in_time = false;
break;
}
int day_capacity = (active_day % 2 == 1) ? mid_cap : (mid_cap / 2);
if (weights[pkg_idx] > day_capacity) {
active_day++;
loaded_weight = 0;
continue;
}
if (loaded_weight + weights[pkg_idx] <= day_capacity) {
loaded_weight += weights[pkg_idx];
pkg_idx++;
} else {
active_day++;
loaded_weight = 0;
}
}
if (fits_in_time && active_day <= days) {
min_required_capacity = mid_cap;
end_cap = mid_cap - 1;
} else {
start_cap = mid_cap + 1;
}
}
return min_required_capacity;
}
August 2, 2026 1.1K 1
