https://www.acmicpc.net/problem/24041

핵심 아이디어

<aside> 💡

며칠 까지 먹을 수 있는지 이분탐색 한다.

뺄 수 없는 재료는 전부 넣고 뺄 수 있는 재료는 세균 수가 적은 순서대로 최대한 넣는다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int N, G, K;
vector<pair<int, int>> nes;
vector<pair<int, int>> cr;

signed main()
{
    FASTIO;
    cin >> N >> G >> K;
    for(int i = 0; i<N; i++){
        int s, l, o;
        cin >> s >> l >> o;
        if(o) cr.push_back({s, l});
        else nes.push_back({s, l});
    }

    ll lo = 1, hi = 2e+9+1;
    while(lo+1<hi){
        ll x = lo+hi>>1;

        ll cur = 0ll;
        for(auto[s, l]: nes){
            cur += 1LL * s * max(1ll, x-l);
        }
        
        vector<ll> sel(cr.size());
        for(int i = 0; i<cr.size(); i++){
            sel[i] = 1LL * cr[i].first * max(1LL, x-cr[i].second);
        }
        sort(sel.begin(), sel.end());
        for(int i = 0; i<max(0, int(cr.size())-K); i++){
            cur += sel[i];
        }

        if(cur<=G) lo = x;
        else hi = x;
    }
    cout << lo;
    return 0;
}