Advertisement
rembocoder

Untitled

Mar 17th, 2023
340
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. const int mod = 998244353;
  8. const int max_sum = 1e5 + 1;
  9.  
  10. int32_t main() {
  11.     ios_base::sync_with_stdio(false);
  12.     cin.tie(0); cout.tie(0);
  13.     int n;
  14.     cin >> n;
  15.     vector<pair<int, pair<int, int>>> ev; // l, t (0 = seg, 1 = query), ind
  16.     vector<int> seg_r(n), seg_cost(n);
  17.     for (int i = 0; i < n; i++) {
  18.         int seg_l;
  19.         cin >> seg_cost[i] >> seg_l >> seg_r[i];
  20.         ev.push_back({seg_l, {0, i}});
  21.     }
  22.     int m;
  23.     cin >> m;
  24.     vector<int> q_sum(m), q_r(m);
  25.     for (int i = 0; i < m; i++) {
  26.         int q_l;
  27.         cin >> q_l >> q_sum[i] >> q_r[i];
  28.         q_r[i] += q_l;
  29.         ev.push_back({q_l, {1, i}});
  30.     }
  31.     sort(ev.begin(), ev.end());
  32.     vector<bool> ans(m);
  33.     vector<int> dp(max_sum, -2e18);
  34.     dp[0] = 2e18;
  35.     for (auto event: ev) {
  36.         int t = event.second.first, ind = event.second.second;
  37.         if (t == 1) {
  38.             ans[ind] = dp[q_sum[ind]] > q_r[ind];
  39.             continue;
  40.         }
  41.         for (int s = max_sum - 1; s >= seg_cost[ind]; s--) {
  42.             dp[s] = max(dp[s], min(dp[s - seg_cost[ind]], seg_r[ind]));
  43.         }
  44.     }
  45.     for (int i = 0; i < m; i++) {
  46.         cout << (ans[i] ? "YES\n" : "NO\n");
  47.     }
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement