oj.uz

답안 #489017

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489017 2021-11-21T03:32:51 Z prime_modulus Knapsack (NOI18_knapsack) Java 11
0 / 100
 1000 ms 9888 KB 
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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 9556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 8476 KB Output is correct
2 Execution timed out 1092 ms 9888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 8476 KB Output is correct
2 Execution timed out 1092 ms 9888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 9556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 9556 KB Time limit exceeded
2 Halted 0 ms 0 KB -