Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- using namespace std;
- int main() {
- ofstream out;
- out.open("meetings.out");
- ifstream in;
- in.open("meetings.out");
- int n, k;
- in >> n >> k;
- vector<int> a(n + 1);
- vector<int> b(n + 1);
- vector<int> c(n + 1);
- vector<int> dp(1 << n + 1, 0);
- vector<int> ones(1 << n + 1, 0);
- vector<int> last_meeting(1 << n + 1, 0);
- for (int i = 0; i < n; i++) {
- in >> a[i] >> b[i] >> c[i];
- }
- dp[0] = k;
- int R = 0;
- for (int mask = 1; mask < (1 << n); mask++) {
- dp[mask] = 200;
- for (int x = 0; x < n; x++) {
- if ((mask & (1 << x)) == 0)
- continue;
- int prev_mask = mask & ~(1 << x);
- if (dp[prev_mask] == 200)
- continue;
- if ((dp[prev_mask] >= a[x]) && (dp[prev_mask] <= b[x])) {
- dp[mask] = dp[prev_mask] + c[x];
- ones[mask] = ones[prev_mask] + 1;
- if (ones[mask] > ones[R])
- R = mask;
- last_meeting[mask] = x;
- break;
- }
- }
- }
- vector<int> ans;
- out << ones[R] << endl;
- while (R != 0) {
- ans.push_back(last_meeting[R]);
- R = R & ~(1 << last_meeting[R]);
- }
- for (int i = ans.size() - 1; i >= 0; i--) {
- out << ans[i] + 1 << ' ';
- }
- in.close();
- out.close();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement