Submission #501375

#	Time	Username	Problem	Language	Result	Execution time	Memory
501375		churros	Knapsack (NOI18_knapsack)	Java	12 / 100	76 ms	10144 KiB

knapsack

import java.io.*;
import java.util.*;

public class knapsack {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int maxWeight = Integer.parseInt(st.nextToken());
        int numItemTypes = Integer.parseInt(st.nextToken());
        int[] maxVal = new int[maxWeight + 1];
        int[] itemValue = new int[numItemTypes];
        int[] itemWeight = new int[numItemTypes];
        int[] itemCount = new int[numItemTypes];

        for (int i = 0; i < numItemTypes; i++) {
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            int count = Integer.parseInt(st.nextToken());
            itemValue[i] = value;
            itemWeight[i] = weight;
            itemCount[i] = count;
        }


        for (int i = 0; i < numItemTypes; i++) {
            int[] timesUsed = new int[maxWeight + 1];
            for (int j = 0; j < maxWeight; j++) {
                int targetWeight = itemWeight[i] + j;
                if (targetWeight <= maxWeight) {
                    if (maxVal[targetWeight] < maxVal[j] + itemValue[i]) {
                        if (timesUsed[j] < itemCount[i]) {
                            timesUsed[targetWeight] = timesUsed[j] + 1;
                            maxVal[targetWeight] = maxVal[j] + itemValue[i];
                        }
                    }
                }
            }
        }

        int ret = 0;
        for (int i = 0; i <= maxWeight; i++) {
            ret = Math.max(ret, maxVal[i]);
        }
        pw.println(ret);

        br.close();
        pw.close();
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27