fork download
copy 
  1. // ~~ icebear ~~
  2. // MOB — Pareto + quadratic closed form
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. using ld = long double;
  6.  
  7. struct Item {
  8.     ld w, a, b;
  9. };
  10.  
  11. int main() {
  12.     ios::sync_with_stdio(false);
  13.     cin.tie(nullptr);
  14.     int n;
  15.     ld M;
  16.     cin >> n >> M;
  17.     vector<Item> v(n);
  18.     for (int i = 0; i < n; ++i)
  19.         cin >> v[i].w >> v[i].a >> v[i].b;
  20.  
  21.     // ---- Pareto pruning ----
  22.     vector<pair<ld, ld>> pts;
  23.     for (auto &x : v)
  24.         pts.push_back({x.a / x.w, x.b / x.w});
  25.     vector<int> idx(n);
  26.     iota(idx.begin(), idx.end(), 0);
  27.  
  28.     sort(idx.begin(), idx.end(), [&](int i, int j) {
  29.         auto [ri, si] = pts[i];
  30.         auto [rj, sj] = pts[j];
  31.         if (ri != rj) return ri > rj; // sort by r descending
  32.         return si < sj;               // tie-break by s ascending
  33.     });
  34.  
  35.     vector<Item> keep;
  36.     ld bestS = -1e100;
  37.     for (int id : idx) {
  38.         ld s = pts[id].second;
  39.         if (s > bestS) {
  40.             bestS = s;
  41.             keep.push_back(v[id]);
  42.         }
  43.     }
  44.     int k = keep.size();
  45.  
  46.     // ---- Evaluate ----
  47.     ld ans = 0;
  48.     auto fval = [&](ld ai, ld aj, ld bi, ld bj, ld wi, ld wj, ld x) {
  49.         if (x < 0) return (ld)-1e100;
  50.         ld y = (M - wi * x) / wj;
  51.         if (y < 0) return (ld)-1e100;
  52.         ld A = ai * x + aj * y;
  53.         ld B = bi * x + bj * y;
  54.         return A * B;
  55.     };
  56.  
  57.     for (int i = 0; i < k; ++i) {
  58.         ld wi = keep[i].w, ai = keep[i].a, bi = keep[i].b;
  59.         ld z = M / wi;
  60.         ans = max(ans, (ai * z) * (bi * z));
  61.         for (int j = i + 1; j < k; ++j) {
  62.             ld wj = keep[j].w, aj = keep[j].a, bj = keep[j].b;
  63.             ld p = ai - aj * wi / wj;
  64.             ld q = aj * M / wj;
  65.             ld r = bi - bj * wi / wj;
  66.             ld s = bj * M / wj;
  67.             ld best = max(fval(ai, aj, bi, bj, wi, wj, 0),
  68.                           fval(ai, aj, bi, bj, wi, wj, M / wi));
  69.             if (p * r < 0) {
  70.                 ld xstar = -(p * s + q * r) / (2 * p * r);
  71.                 if (xstar >= 0 && xstar <= M / wi)
  72.                     best = max(best, fval(ai, aj, bi, bj, wi, wj, xstar));
  73.             }
  74.             ans = max(ans, best);
  75.         }
  76.     }
  77.  
  78.     cout << fixed << setprecision(2) << (double)ans << "\n";
  79. }
  80.  
Success #stdin #stdout 0.02s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.00
https://ideone.com/p6ynvA
language:
C++14 (gcc 8.3)
created:
17 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!