Code c++ bài Phần thưởng trong Đề thi OLP Miền Trung Tây Nguyên bảng Không chuyên vòng chung kết năm 2023

#include <bits/stdc++.h>
 
#define ll long long
#define fi first
#define sc second
 
using namespace std;

 void io(){
     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 }

int main(){
    io();
    ll n,s;
    cin >> n>> s;
    ll sum =0;
    ll totalw=0;
    vector<pair<ll,ll>> ct,cs;
    for (int i=0;i<n;i++){
        ll w,v,c;

        cin >> w >> v >> c;

        if (c==0) cs.push_back({w,v}); else {
            ct.push_back({w,v});
            sum+=v;
            totalw+=w;
        }
    }
    sort(ct.begin(),ct.end());
    sort(cs.begin(),cs.end());
    ll d1=ct.size();
    ll d2=cs.size();
    ll j=0;
    if (d2==0) {
        cout << sum ;
        return 0;
    }
    ll ans = sum;
    ll f[d2]{};
    f[0]=cs[0].sc;
    for (int i=1;i<d2;i++){
        f[i]=max(f[i-1],cs[i].sc);
    }
    if (d1==0) {
        cout << f[n-1];
        return 0;
    }
    // for (auto i : cs) cout << i.fi << ' '<< i.sc << '\n';
    for (int i=0;i<d1;i++){
        if (cs[j].fi+totalw-ct[i].fi<=s&&j<d2){
        while (cs[j].fi+totalw-ct[i].fi<=s&&j<d2){
            ans = max(ans,sum-ct[i].sc+f[j]);
            j++;
        }
        j--;
    }
        if (j==d2) j--;
    }
    cout << ans;
}