Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(l) cerr<<#l<<' '<<l<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(mask) mask.begin(), mask.end()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef pair<int, int> pii;
- typedef long double ld;
- ld gen() {
- ll x = rand() + 1;
- ll y = rand() + 1;
- x %= y;
- return (ld)x / (ld)y;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- srand(time(NULL));
- int n;
- cin >> n;
- int k;
- cin >> k;
- struct event {
- int a, b, c;
- };
- vector<event> a(n);
- for (int i = 0; i < n; i++) {
- cin >> a[i].a >> a[i].b >> a[i].c;
- }
- vector<int> p(n);
- for (int i = 0; i < n; i++) {
- p[i] = i;
- }
- int now_res = 0;
- int best_res = 0;
- vector<int> best_p;
- best_p = p;
- auto count = [&](vector<int>& d) {
- int sum = k;
- int res = 0;
- for (int i = 0; i < n; i++) {
- if (sum >= a[d[i]].a && sum <= a[d[i]].b) {
- sum += a[d[i]].c;
- res++;
- }
- }
- return res;
- };
- now_res = best_res = count(p);
- while(1){
- ld t0 = 1.0000, q1 = 0.995;
- while(t0>1e-6) {
- if ((double)clock() / (double)CLOCKS_PER_SEC >= 1.8999) {
- cout << best_res << '\n';
- int sum = k;
- int res = 0;
- vector<int> anse;
- for (int i = 0; i < n; i++) {
- if (sum >= a[best_p[i]].a && sum <= a[best_p[i]].b) {
- sum += a[best_p[i]].c;
- anse.push_back(best_p[i]);
- }
- }
- for (int& i : anse) {
- cout << i + 1 << ' ';
- }
- return 0;
- }
- vector<int> q = p;
- for (int j = 0; j < n * t0; j++) {
- int l = rand() % n, r = rand() % n;
- swap(q[l], q[r]);
- }
- int cnt = count(q);
- if (cnt > best_res) {
- best_res = cnt;
- best_p = q;
- p = q;
- }
- if (gen() < exp((cnt - now_res) / t0)) {
- now_res = cnt;
- p = q;
- }
- t0 *= q1;
- }
- }
- cout << best_res << '\n';
- int sum = k;
- int res = 0;
- vector<int> anse;
- for (int i = 0; i < n; i++) {
- if (sum >= a[best_p[i]].a && sum <= a[best_p[i]].b ) {
- sum += a[best_p[i]].c;
- anse.push_back(best_p[i]);
- }
- }
- for (int& i : anse) {
- cout << i + 1<< ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement