Submission #489017

#	Time	Username	Problem	Language	Result	Execution time	Memory
489017		prime_modulus	Knapsack (NOI18_knapsack)	Java	0 / 100	1092 ms	9888 KiB

knapsack

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

public class knapsack {
    public static void main(String[] args) throws IOException {
        setIO();

        st = nl();
        int S = ni(st), N = ni(st);
        int[] V = new int[N];
        int[] W = new int[N];
        int[] K = new int[N];
        for (int i = 0; i < N; i++) {
            st = nl();
            V[i] = ni(st);
            W[i] = ni(st);
            K[i] = ni(st);
            K[i] = Math.max(K[i], S / W[i]);
        }

        int[][] dp = new int[N+1][S+1];
        for (int i = 1; i <= N; i++) {
            for (int s = 1; s <= S; s++) {
                for (int k = 0; k <= K[i-1]; k++) {
                    if (s >= k * W[i-1]) dp[i][s] = Math.max(dp[i][s], k * V[i-1] + dp[i-1][s - k * W[i-1]]);
                }
            }
        }

        out.println(dp[N][S]);

        closeIO();
    }

    static BufferedReader f;
    static PrintWriter out;
    static StringTokenizer st;

    static final int MOD = 1000000007;

    static String rl() throws IOException {
        return f.readLine();
    }

    static int ni(StringTokenizer st) {
        return Integer.parseInt(st.nextToken());
    }

    static long nlg(StringTokenizer st) {
        return Long.parseLong(st.nextToken());
    }

    static int ni() throws IOException {
        return Integer.parseInt(rl());
    }

    static long nlg() throws IOException {
        return Long.parseLong(rl());
    }

    static StringTokenizer nl() throws IOException {
        return new StringTokenizer(rl());
    }

    static int[] nia(int N) throws IOException {
        StringTokenizer st = nl();
        int[] A = new int[N];
        for (int i = 0; i < N; i++)
            A[i] = ni(st);
        return A;
    }

    static void setIn(String s) throws IOException {
        f = new BufferedReader(new FileReader(s));
    }

    static void setOut(String s) throws IOException {
        out = new PrintWriter(new FileWriter(s));
    }

    static void setIn() {
        f = new BufferedReader(new InputStreamReader(System.in));
    }

    static void setOut() {
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    }

    static void setIO(String s) throws IOException {
        setIn(s + ".in");
        setOut(s + ".out");
    }

    static void setTextIO(String s) throws IOException {
        setIn(s + ".txt");
        setOut(s + "_out.txt");
    }

    static void setIO() {
        setIn();
        setOut();
    }

    static void closeIO() throws IOException {
        f.close();
        out.close();
    }
}

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