Advertisement
senb1

krsu 3404 (not my code)

Mar 29th, 2023
570
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define ar array
  5. typedef long long ll;
  6.  
  7. const int N = 1e5 + 5;
  8. int x[N], y[N], z[N];
  9. ll res_pref[N], res_suff[N];
  10.  
  11. signed main() {
  12.     ios::sync_with_stdio(0);
  13.     cin.tie(0);
  14.  
  15.     int X, Y, Z;
  16.     cin >> X >> Y >> Z;
  17.     int n = X + Y + Z;
  18.     for (int i = 0; i < n; i++) {
  19.         cin >> x[i] >> y[i] >> z[i];
  20.     }
  21.     vector<int> p(n);
  22.     iota(p.begin(), p.end(), 0);
  23.     sort(p.begin(), p.end(),
  24.          [&](int i, int j) { return y[i] - x[i] < y[j] - x[j]; });
  25.  
  26.     ll ans = 0;
  27.     priority_queue<int> pref, suff;
  28.     for (int i = 0; i < n; i++) {
  29.         if (i)
  30.             res_pref[i] = res_pref[i - 1];
  31.         res_pref[i] += x[p[i]];
  32.         pref.push(z[p[i]] - x[p[i]]);
  33.         if (i >= X) {
  34.             res_pref[i] += pref.top();
  35.             pref.pop();
  36.         }
  37.     }
  38.  
  39.     for (int i = n - 1; ~i; i--) {
  40.         if (i + 1 < n)
  41.             res_suff[i] = res_suff[i + 1];
  42.         res_suff[i] += y[p[i]];
  43.         suff.push(z[p[i]] - y[p[i]]);
  44.         if (i + Y < n) {
  45.             res_suff[i] += suff.top();
  46.             suff.pop();
  47.         }
  48.     }
  49.  
  50.     for (int i = X - 1; i + Y < n; i++) {
  51.         ans = max(ans, res_pref[i] + res_suff[i + 1]);
  52.     }
  53.  
  54.     cout << ans << "\n";
  55. }
  56.  
  57. /*
  58.  
  59. 1 2 1
  60. 2 4 4
  61. 3 2 1
  62. 7 6 7
  63. 5 2 3
  64.  
  65. */
  66.  
Advertisement
Comments
  • senb1
    1 year
    # text 0.15 KB | 0 0
    1. (~i) means (i != -1), how I understood. these solutions are so difficult, I can't really understand them, maybe I just haven't solved that many to understand
Add Comment
Please, Sign In to add comment
Advertisement