Language: C++

#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

typedef __float128 dbl;
const int INF = 1.01e9;
 
const __float128 EPS = 1e-25;
bool eq(__float128 x, __float128 y) {
    return fabs(x - y) < EPS;
}
bool ls(__float128 x, __float128 y) {
    return x < y && !eq(x, y);
}
 
vector<__float128> simplex(vector<vector<__float128> > a) {
    int n = a.size() - 1;
    int m = a[0].size() - 1;
    vector<int> left(n + 1), up(m + 1);
    iota(up.begin(), up.end(), 0);
    iota(left.begin(), left.end(), m);
    auto pivot = [&](int x, int y) {
        swap(left[x], up[y]);
        __float128 k = a[x][y];
        a[x][y] = 1;
        vector<int> vct;
        for (int j = 0; j <= m; j++) {
            a[x][j] /= k;
            if (!eq(a[x][j], 0)) vct.push_back(j);
        }
        for (int i = 0; i <= n; i++) {
            if (eq(a[i][y], 0) || i == x) continue;
            k = a[i][y];
            a[i][y] = 0;
            for (int j : vct) a[i][j] -= k * a[x][j];
        }
    };
    while (1) {
        int x = -1;
        for (int i = 1; i <= n; i++) if (ls(a[i][0], 0) && (x == -1 || a[i][0] < a[x][0])) x = i;
        if (x == -1) break;
        int y = -1;
        for (int j = 1; j <= m; j++) if (ls(a[x][j], 0) && (y == -1 || a[x][j] < a[x][y])) y = j;
        if (y == -1) assert(0); // infeasible
        pivot(x, y);
    }
    while (1) {
        int y = -1;
        for (int j = 1; j <= m; j++) if (ls(0, a[0][j]) && (y == -1 || a[0][j] > a[0][y])) y = j;
        if (y == -1) break;
        int x = -1;
        for (int i = 1; i <= n; i++) if (ls(0, a[i][y]) && (x == -1 || a[i][0] / a[i][y] < a[x][0] / a[x][y])) x = i;
        if (x == -1) assert(0); // unbounded
        pivot(x, y);
    }
    vector<__float128> ans(m + 1);
    for (int i = 1; i <= n; i++) if (left[i] <= m) ans[left[i]] = a[i][0];
    ans[0] = -a[0][0];
    return ans;
}

#ifdef ONPC
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

int main()
{
#ifdef ONPC
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector <int> x(n), y(n);
  vector <ll> ok;
  vector <__float128> v;
  vector <pair <ll, int> > e;
  for (int i = 0; i < n; i++)
  {
    cin >> x[i] >> y[i];
    ll x;
    cin >> x;
    ok.push_back(x);
    v.push_back(x);
    e.push_back({x, i});
  }
  v.insert(v.begin(), 0);
  int m;
  cin >> m;
  vector <vector <__float128> > mat;
  mat.push_back(v);
  for (int i = 0; i < n; i++)
  {
    vector <__float128> kek(n + 1);
    kek[0] = kek[i + 1] = 1;
    mat.push_back(kek);
  }
  vector <vector <int> > simp;
  for (int i = 0; i < m; i++)
  {
    char c;
    cin >> c;
    int a;
    int b;
    cin >> a >> b;
    vector <__float128> arr = {(__float128) b};
    vector <int> kek = {b};
    for (int j = 0; j < n; j++)
    {
      int grab = 0;
      if (c == 'L' && x[j] <= a) grab = 1;
      if (c == 'R' && x[j] >= a) grab = 1;
      if (c == 'D' && y[j] <= a) grab = 1;
      if (c == 'U' && y[j] >= a) grab = 1;
      arr.push_back(grab);
      kek.push_back(grab);
    }
    mat.push_back(arr);
    simp.push_back(kek);
  }
  auto good = [&] (vector <int> grab)
  {
    for (auto c : simp)
    {
      int sum = 0;
      for (int i = 1; i <= n; i++) sum += grab[i - 1] * c[i];
      if (sum > c[0])
      {
        return false;
      }
    }
    return true;
  };
  auto f = [&] (vector <int> grab)
  {
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
      if (grab[i]) sum += ok[i];
    }
    return sum;
  };
  vector <int> grab;
  for (int i = 0; i < n; i++) grab.push_back(0);
  cout.precision(20);
  auto solve = [&] ()
  {
    auto ret = simplex(mat);
    sort(e.begin(), e.end());
    vector <int> me(n);
    int x = -1;
    for (int i = 1; i <= n; i++)
    {
      if (grab[i - 1]) continue;
      grab[x - 1] = true;
      if (!good(grab))
      {
        grab[x - 1] = false;
        continue;
      }
      if (x == -1 || ret[i] > ret[x])
      {
        x = i;
      }
    }
    if (x == -1 || ret[x] < EPS) return 0ll;
    x--;
    me[x] = true;
    grab[x] = true;
    if (!good(grab)) grab[x] = false, me[x] = false;
    int kekos = 0;
    for (auto &c : mat)
    {
      kekos++;
      if (kekos > n + 1)
      for (int i = 1; i <= n; i++)
      {
        if (me[i - 1] && c[i] > EPS) c[i]--, c[0]--;
      }
    }
    for (int i = 1; i <= n; i++)
    {
      if (me[i - 1])
      {
        mat[i][0] = 0;
      }
    }
    return ok[x];
  };
  ll ans = 0;
  while (ll t = solve())
  {
    ans += t;
  }
  cout << ans << endl;
}


Compiler output:
a.cc: In function 'bool eq(__float128, __float128)':
a.cc:32:16: error: call of overloaded 'fabs(__float128)' is ambiguous
   32 |     return fabs(x - y) < EPS;
      |            ~~~~^~~~~~~
In file included from /usr/include/features.h:523,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/os_defines.h:39,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/c++config.h:683,
                 from /usr/include/c++/14/bits/requires_hosted.h:31,
                 from /usr/include/c++/14/cmath:41,
                 from a.cc:1:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:195:1: note: candidate: 'double fabs(double)'
  195 | __MATHCALLX (fabs,, (_Mdouble_ __x), (__const__));
      | ^~~~~~~~~~~
/usr/include/c++/14/cmath:242:3: note: candidate: 'constexpr long double std::fabs(long double)'
  242 |   fabs(long double __x)
      |   ^~~~
/usr/include/c++/14/cmath:238:3: note: candidate: 'constexpr float std::fabs(float)'
  238 |   fabs(float __x)
      |   ^~~~