Submission #62053559

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)5e3+10;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
const int MOD = (int)1e9+7;

int n, X;
vector<ar2> v[3];
int dp[3][mxN];
string s[mxN];

void solve(){
    cin >> n >> X;
    for(int i = 0; i < n; i++){
        int xd, a, c; 
        cin >> xd >> a >> c;
        v[xd-1].pb({a,c});
    }
    for(int _ = 0; _ < 3; _++){
        for(int i = 1; i <= sz(v[_]); i++)
            for(int j = 5000; j>=v[_][i-1][1]; j--)
                dp[_][j] = max(dp[_][j], dp[_][j-v[_][i-1][1]]+v[_][i-1][0]);
        for(int i = 1; i <= 5000; i++) 
            dp[_][i]=max(dp[_][i],dp[_][i-1]);
    }
    int ans = 0;
    for(int i = 0; i <= X; i++){
        for(int j = 0; i+j <= X; j++){
            int rem = X-(i+j);
            ans = max(ans, min({dp[0][i],dp[1][j],dp[2][rem]}));
        }
    }
    cout << ans << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
}

Submission Info

Judge Result