Submission #62083348

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
        f = (c == '-') ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9')
        x = x * 10 + c - 48, c = getchar();
    return f * x;
}
struct node {
    int v, a, c;
} a[10010];
int n, x;
int f[4][5010];
int dp[4][5010];
int maxx = 0;
void check() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= x; j++) {
            if(j >= a[i].c)
                f[a[i].v][j] = max(dp[a[i].v][j], dp[a[i].v][j - a[i].c] + a[i].a);
            else
                f[a[i].v][j] = dp[a[i].v][j];
        }
        for(int j = 1; j <= x; j++)
            dp[a[i].v][j] = f[a[i].v][j];
    }
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= x; j++)
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
    for(int i = 1; i <= x; i++)
        for(int j = 1; j <= x - i; j++) {
            maxx = max(maxx, min(dp[1][i], min(dp[2][j], dp[3][x - i - j])));
        }
}
signed main() {
    n = read(), x = read();
    for(int i = 1; i <= n; i++) {
        a[i] = {read(), read(), read()};
    }
    check();
    cout << maxx;
}

Submission Info

Judge Result