ABC390

E - Vitamin Balance

#include <bits/stdc++.h>
using namespace std;
int n, x;
// <维生素量,卡路里量>
// a[1] 存维生素 1，a[2] ~
vector<pair<int, int>> a[5];
// [typ][i][j] 第 typ 种维生素
// 前 i 个，在 j 的卡路里时，最多能拿到多少维生素量
int f[5][5005][5005];
// 三种维生素，都拿到 low 及以上的量，能否在 x 的卡路里以内完成
bool check(int low)
{
    int sum = 0;
    for (int typ = 1; typ <= 3; typ++)
    {
        if (f[typ][a[typ].size()][x] < low)
            return false;
        int now; // 第 typ 中维生素达到 low 及以上的量的最小卡路里
        int l = 0;
        int r = x;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (f[typ][a[typ].size()][mid] >= low)
            {
                now = mid;
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        sum += now;
    }
    return sum <= x;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
    {
        int vi, ai, ci;
        cin >> vi >> ai >> ci;
        a[vi].push_back(make_pair(ai, ci));
    }

    for (int typ = 1; typ <= 3; typ++)
    {
        for (int i = 1; i <= a[typ].size(); i++)
        {
            int v = a[typ][i - 1].first;  // typ 维生素的第 i 个的维生素量
            int c = a[typ][i - 1].second; // ~ 卡路里量
            for (int j = 0; j <= x; j++)
            {
                if (j < c)
                    f[typ][i][j] = f[typ][i - 1][j];
                else
                    f[typ][i][j] = max(f[typ][i - 1][j],
                                       f[typ][i - 1][j - c] + v);
            }
        }
    }

    int l = 0;
    int r = 1'000'000'000;
    int ans = -1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    cout << ans;
    return 0;
}