Submission #62060590

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main() {
    #ifdef ABHISHEK_SRIVASTAVA
        freopen("Input.txt", "r", stdin);
        freopen("Output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, x;
    cin >> n >> x;
    long long cals[3][x + 1], lo = 0, hi, res;
    memset(cals, 0, sizeof(cals));
    while (n--) {
        int v, a, c;
        cin >> v >> a >> c;
        for (int i = x; i >= c; i--)
            cals[v - 1][i] = max(cals[v - 1][i], cals[v - 1][i - c] + a);
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

int main() {
    #ifdef ABHISHEK_SRIVASTAVA
        freopen("Input.txt", "r", stdin);
        freopen("Output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, x;
    cin >> n >> x;
    long long cals[3][x + 1], lo = 0, hi, res;
    memset(cals, 0, sizeof(cals));
    while (n--) {
        int v, a, c;
        cin >> v >> a >> c;
        for (int i = x; i >= c; i--)
            cals[v - 1][i] = max(cals[v - 1][i], cals[v - 1][i - c] + a);
    }
    hi = min({cals[0][x], cals[1][x], cals[2][x]});
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        if ((lower_bound(cals[0], cals[0] + x + 1, mid) - cals[0] +
            lower_bound(cals[1], cals[1] + x + 1, mid) - cals[1] +
            lower_bound(cals[2], cals[2] + x + 1, mid) - cals[2]) > x) 
                hi = mid - 1;
        else {
            res = mid;
            lo = mid + 1;
        }    
    }
    cout << res;

    return 0;
}

Submission Info

Judge Result