Submission #62096909

Source Code Expand

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;

using ll = long long;

#define rep(i, n) for(int i = 0; (i) < (int)(n); ++(i))
#define rep_r(i, n) for(int i = (int)(n) - 1; (i) >= 0; --(i))
#define all(x) begin(x), end(x)

int main() {
    // input
    int N, X;
    cin >> N >> X;
    vector<int> V(N), A(N), C(N);
    rep(i, N) cin >> V[i] >> A[i] >> C[i];

    // calc
    vector<vector<vector<ll>>> memory(
        N, vector<vector<ll>>(X + 1, vector<ll>(3, 0)));
    rep(i, N) {
        if(i == 0) {
            rep(x, X + 1) {
                if(C[i] >= x) memory[i][x][V[i] - 1] = A[i];
            }
        } else {
            rep(x, X + 1) {
                if(x < C[i]) {
                    memory[i][x] = memory[i - 1][x];
                } else {
                    ll old_score = *min_element(all(memory[i - 1][x]));

                    vector<ll> new_scores(memory[i][x - C[i]]);
                    new_scores[V[i] - 1] += A[i];
                    ll new_score = *min_element(all(new_scores));

                    if(old_score >= new_score) {
                        memory[i][x] = memory[i - 1][x];
                    } else {
                        memory[i][x] = new_scores;
                    }
                }
            }
        }
    }
    ll result = *min_element(all(memory[N - 1][X]));

    // output
    cout << result << endl;
}

Submission Info

Submission Time
Task E - Vitamin Balance
User Koreander
Language C++ 23 (gcc 12.2)
Score 0
Code Size 1419 Byte
Status WA
Exec Time 1615 ms
Memory 1371288 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 450
Status
AC × 1
WA × 1
AC × 3
WA × 50
MLE × 5
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_40.txt, random_41.txt, random_42.txt, random_43.txt, random_44.txt
Case Name Status Exec Time Memory
example_00.txt WA 1 ms 3600 KiB
example_01.txt AC 2 ms 3956 KiB
hand_00.txt WA 1 ms 3592 KiB
hand_01.txt WA 926 ms 775148 KiB
hand_02.txt WA 2 ms 4344 KiB
hand_03.txt MLE 1452 ms 1371288 KiB
hand_04.txt WA 6 ms 7640 KiB
hand_05.txt WA 1 ms 3476 KiB
hand_06.txt MLE 1615 ms 1371184 KiB
hand_07.txt MLE 1269 ms 1371268 KiB
hand_08.txt AC 2 ms 3932 KiB
hand_09.txt AC 1 ms 3596 KiB
hand_10.txt MLE 1604 ms 1371168 KiB
random_00.txt WA 11 ms 12096 KiB
random_01.txt WA 10 ms 11644 KiB
random_02.txt WA 10 ms 12092 KiB
random_03.txt WA 14 ms 14896 KiB
random_04.txt WA 16 ms 15896 KiB
random_05.txt WA 13 ms 15120 KiB
random_06.txt WA 25 ms 24144 KiB
random_07.txt WA 58 ms 50748 KiB
random_08.txt WA 20 ms 20856 KiB
random_09.txt WA 81 ms 68896 KiB
random_10.txt WA 102 ms 87428 KiB
random_11.txt WA 203 ms 192200 KiB
random_12.txt WA 474 ms 406084 KiB
random_13.txt WA 461 ms 392312 KiB
random_14.txt WA 777 ms 731288 KiB
random_15.txt WA 16 ms 16348 KiB
random_16.txt WA 14 ms 14756 KiB
random_17.txt WA 10 ms 11936 KiB
random_18.txt WA 3 ms 5816 KiB
random_19.txt WA 13 ms 13428 KiB
random_20.txt WA 15 ms 15792 KiB
random_21.txt WA 55 ms 49320 KiB
random_22.txt WA 39 ms 35504 KiB
random_23.txt WA 18 ms 18264 KiB
random_24.txt WA 158 ms 135992 KiB
random_25.txt WA 105 ms 88408 KiB
random_26.txt WA 292 ms 247056 KiB
random_27.txt WA 760 ms 643588 KiB
random_28.txt WA 912 ms 778124 KiB
random_29.txt WA 346 ms 291508 KiB
random_30.txt WA 10 ms 11336 KiB
random_31.txt WA 12 ms 12992 KiB
random_32.txt WA 12 ms 13248 KiB
random_33.txt WA 12 ms 12788 KiB
random_34.txt WA 5 ms 6720 KiB
random_35.txt WA 8 ms 10016 KiB
random_36.txt WA 7 ms 8692 KiB
random_37.txt WA 30 ms 28460 KiB
random_38.txt WA 45 ms 40516 KiB
random_39.txt WA 19 ms 19604 KiB
random_40.txt WA 96 ms 81584 KiB
random_41.txt WA 49 ms 43288 KiB
random_42.txt WA 1005 ms 843180 KiB
random_43.txt MLE 1362 ms 1159732 KiB
random_44.txt WA 101 ms 85088 KiB