#54689: Cpp EZ
belubruh123
(belubruh123)
#include <bits/stdc++.h>
using namespace std;
int n;
// tasks[i][0] = start, tasks[i][1] = deadline, tasks[i][2] = processing time
// Max N is 10, so size 15 is plenty safe.
int tasks[15][3];
bool check(int x) {
int INF = 999999; // A simple large number to act as "infinity"
int dp[1024]; // 2^10 = 1024, enough to hold all bitmask states
// Initialize the DP array to INF
for (int i = 0; i < (1 << n); i++) {
dp[i] = INF;
}
dp[0] = -INF; // Base case: 0 tasks done ends at negative infinity
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == INF) continue; // Skip unreachable states
for (int i = 0; i < n; i++) {
// Check if the i-th bit is 0 (meaning task i is NOT done yet)
if (!(mask & (1 << i))) {
int start_time = tasks[i][0];
// If it's not the very first task, add the rest time 'x'
if (mask != 0) {
start_time = max(start_time, dp[mask] + x);
}
int finish_time = start_time + tasks[i][2];
// If it finishes before or exactly on the deadline
if (finish_time <= tasks[i][1]) {
int next_mask = mask | (1 << i); // Turn on the i-th bit
dp[next_mask] = min(dp[next_mask], finish_time);
}
}
}
}
// If the state where ALL tasks are done is not INF, it's possible
return dp[(1 << n) - 1] != INF;
}
int main() {
cin >> n;
int max_d = 0;
for (int i = 0; i < n; i++) {
cin >> tasks[i][0] >> tasks[i][1] >> tasks[i][2];
max_d = max(max_d, tasks[i][1]);
}
if (n == 1) {
cout << 0 << endl;
return 0;
}
// Binary search for the maximum possible rest time
int low = 0;
int high = max_d;
int ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (check(mid)) {
ans = mid; // mid is possible, save it
low = mid + 1; // try to find a bigger rest time
} else {
high = mid - 1; // mid is too big, shrink the search space
}
}
cout << ans << endl;
return 0;
}