comida(2019).cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ponto
{
    ll x, y;

    ponto(ll X = 0, ll Y = 0) : x(X), y(Y) {}

    ponto operator+ (ponto outro) {return ponto(x + outro.x, y + outro.y);}
    ponto operator- (ponto outro) {return ponto(x - outro.x, y - outro.y);}
    long long operator* (ponto outro) {return (x * outro.x) + (y*outro.y);}
    long long operator^ (ponto outro) {return (x * outro.y) - (y*outro.x);}

    bool operator< (ponto outro) {return (x == outro.x ? y > outro.y : x < outro.x);}
};

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll N, R;
    cin >> N >> R;

    vector<tuple<long double, ll, ll>> slopes; //coef, dp, ds
    ll resp = 0;
    for (int i = 1; i <= N; i++)
    {
        int K;
        cin >> K;
        vector<ponto> v(K);
        for (auto &p : v) cin >> p.x >> p.y;
        sort(v.begin(), v.end()); //ordena os pontos por menor preco
        vector<ponto> hull;
        for (auto p : v)
        {
            if (!hull.empty() && hull.back().y > p.y) continue; //se o ponto tem sabor menor que o anterior, nao coloco ele
            int tam = hull.size();
            while (tam >= 2 && ((hull.back() - hull[tam-2])^(p - hull.back())) >= 0) hull.pop_back(), --tam;
            hull.push_back(p);
        }
        R -= hull[0].x; resp += hull[0].y;
        if (R < 0) {cout << -1 << '\n'; return 0;}
        for (int j = 1; j < hull.size(); j++) 
        {
          long double coef = (double)(hull[j].y - hull[j-1].y) / (double)(hull[j].x - hull[j-1].x);
          ll dp = hull[j].x - hull[j-1].x;
          ll ds = hull[j].y - hull[j-1].y;
          slopes.emplace_back(coef, dp, ds);
        }
    }

    //ordena as retas por maior coeficiente
    sort(slopes.begin(), slopes.end(), [&](const tuple<long double, ll, ll> &a, const tuple<long double, ll, ll> &b) {
        if (get<0>(a) == get<0>(b)) return (get<1>(a) == get<1>(b) ? get<2>(a) > get<2>(b) : get<1>(a) < get<1>(b));
        return get<0>(a) > get<0>(b);
    });

    for (int i = 0; i < slopes.size() && R > 0; i++)
    {
        auto [coef, dp, ds] = slopes[i];
        if (dp <= R) resp += ds, R -= dp; //Se tenho mais dinheiro do que eh possivel gastar na reta, uso ela inteira
        else resp += (ll)(coef * R), R = 0; //Senao, faco a conta de quanto sabor consigo com essa reta
    }

    cout << resp << '\n';
}

É possível que exista um erro nesse código, mas é problema pro leitor 👍

É possível que exista um erro nesse código, mas é problema pro leitor 👍

Mlk, checa direito aí. Larga de ser preguiçoso.

É possível que exista um erro nesse código, mas é problema pro leitor 👍

Mlk, checa direito aí. Larga de ser preguiçoso.

Nuh uh