oj.uz

Submission #900181

# Submission time Handle Problem Language Result Execution time Memory
900181 2024-01-07T20:26:53 Z jkwn Knapsack (NOI18_knapsack) Java 11
73 / 100
 361 ms 262144 KB 
import java.io.*;
import java.util.StringTokenizer;

public class knapsack {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(in.readLine());

        int s = Integer.parseInt(tokenizer.nextToken());
        int n = Integer.parseInt(tokenizer.nextToken());
        item[] items = new item[n+1];
        for (int i = 1; i < n+1; i++) {
            tokenizer = new StringTokenizer(in.readLine());
            items[i] = new item(Integer.parseInt(tokenizer.nextToken()),Integer.parseInt(tokenizer.nextToken()),Integer.parseInt(tokenizer.nextToken()));
        }

        int[][] dp = new int[n+1][s+1];
        for (int i = 0; i < n+1; i++) {
            for (int j = 0; j < s+1; j++) {
                dp[i][j] = -1;
            }
        }
        dp[0][0] = 0;

        for (int i = 0; i < n; i++) {
            int v = items[i+1].v;
            int w = items[i+1].w;
            int k = items[i+1].k;
            for (int j = 0; j < s+1; j++) {
                if (dp[i][j] >= 0) {
                    for (int count = 0; count <= k; count++) {
                        if (j + w * count <= s) {
                            dp[i+1][j+w*count] = Math.max(dp[i+1][j+w*count], dp[i][j] + v*count);
                        }
                        else {
                            break;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i < n+1; i++) {
            for (int j = 0; j < s+1; j++) {
                ans = Math.max(ans, dp[i][j]);
            }
        }
        System.out.println(ans);
    }
    static class item {
        int v, w, k;
        item(int v, int w, int k) {
            this.v = v;
            this.w = w;
            this.k = k;
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 22504 KB Output is correct
2 Correct 48 ms 24424 KB Output is correct
3 Correct 48 ms 22080 KB Output is correct
4 Correct 52 ms 22372 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22600 KB Output is correct
2 Correct 67 ms 23956 KB Output is correct
3 Correct 69 ms 23072 KB Output is correct
4 Correct 71 ms 25688 KB Output is correct
5 Correct 71 ms 23672 KB Output is correct
6 Correct 72 ms 24012 KB Output is correct
7 Correct 72 ms 23796 KB Output is correct
8 Correct 67 ms 23784 KB Output is correct
9 Correct 69 ms 27756 KB Output is correct
10 Correct 67 ms 23468 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 22600 KB Output is correct
2 Correct 67 ms 23956 KB Output is correct
3 Correct 69 ms 23072 KB Output is correct
4 Correct 71 ms 25688 KB Output is correct
5 Correct 71 ms 23672 KB Output is correct
6 Correct 72 ms 24012 KB Output is correct
7 Correct 72 ms 23796 KB Output is correct
8 Correct 67 ms 23784 KB Output is correct
9 Correct 69 ms 27756 KB Output is correct
10 Correct 67 ms 23468 KB Output is correct
11 Correct 60 ms 21852 KB Output is correct
12 Correct 68 ms 23808 KB Output is correct
13 Correct 66 ms 23428 KB Output is correct
14 Correct 70 ms 24060 KB Output is correct
15 Correct 69 ms 23724 KB Output is correct
16 Correct 71 ms 23860 KB Output is correct
17 Correct 69 ms 23984 KB Output is correct
18 Correct 69 ms 23088 KB Output is correct
19 Correct 79 ms 24288 KB Output is correct
20 Correct 70 ms 23896 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 22504 KB Output is correct
2 Correct 48 ms 24424 KB Output is correct
3 Correct 48 ms 22080 KB Output is correct
4 Correct 52 ms 22372 KB Output is correct
5 Correct 51 ms 22600 KB Output is correct
6 Correct 67 ms 23956 KB Output is correct
7 Correct 69 ms 23072 KB Output is correct
8 Correct 71 ms 25688 KB Output is correct
9 Correct 71 ms 23672 KB Output is correct
10 Correct 72 ms 24012 KB Output is correct
11 Correct 72 ms 23796 KB Output is correct
12 Correct 67 ms 23784 KB Output is correct
13 Correct 69 ms 27756 KB Output is correct
14 Correct 67 ms 23468 KB Output is correct
15 Correct 60 ms 21852 KB Output is correct
16 Correct 68 ms 23808 KB Output is correct
17 Correct 66 ms 23428 KB Output is correct
18 Correct 70 ms 24060 KB Output is correct
19 Correct 69 ms 23724 KB Output is correct
20 Correct 71 ms 23860 KB Output is correct
21 Correct 69 ms 23984 KB Output is correct
22 Correct 69 ms 23088 KB Output is correct
23 Correct 79 ms 24288 KB Output is correct
24 Correct 70 ms 23896 KB Output is correct
25 Correct 53 ms 24364 KB Output is correct
26 Correct 361 ms 26248 KB Output is correct
27 Correct 70 ms 23744 KB Output is correct
28 Correct 69 ms 26100 KB Output is correct
29 Correct 71 ms 23936 KB Output is correct
30 Correct 71 ms 23604 KB Output is correct
31 Correct 69 ms 23524 KB Output is correct
32 Correct 67 ms 23992 KB Output is correct
33 Correct 69 ms 25852 KB Output is correct
34 Correct 70 ms 23540 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 22504 KB Output is correct
2 Correct 48 ms 24424 KB Output is correct
3 Correct 48 ms 22080 KB Output is correct
4 Correct 52 ms 22372 KB Output is correct
5 Correct 51 ms 22600 KB Output is correct
6 Correct 67 ms 23956 KB Output is correct
7 Correct 69 ms 23072 KB Output is correct
8 Correct 71 ms 25688 KB Output is correct
9 Correct 71 ms 23672 KB Output is correct
10 Correct 72 ms 24012 KB Output is correct
11 Correct 72 ms 23796 KB Output is correct
12 Correct 67 ms 23784 KB Output is correct
13 Correct 69 ms 27756 KB Output is correct
14 Correct 67 ms 23468 KB Output is correct
15 Correct 60 ms 21852 KB Output is correct
16 Correct 68 ms 23808 KB Output is correct
17 Correct 66 ms 23428 KB Output is correct
18 Correct 70 ms 24060 KB Output is correct
19 Correct 69 ms 23724 KB Output is correct
20 Correct 71 ms 23860 KB Output is correct
21 Correct 69 ms 23984 KB Output is correct
22 Correct 69 ms 23088 KB Output is correct
23 Correct 79 ms 24288 KB Output is correct
24 Correct 70 ms 23896 KB Output is correct
25 Correct 53 ms 24364 KB Output is correct
26 Correct 361 ms 26248 KB Output is correct
27 Correct 70 ms 23744 KB Output is correct
28 Correct 69 ms 26100 KB Output is correct
29 Correct 71 ms 23936 KB Output is correct
30 Correct 71 ms 23604 KB Output is correct
31 Correct 69 ms 23524 KB Output is correct
32 Correct 67 ms 23992 KB Output is correct
33 Correct 69 ms 25852 KB Output is correct
34 Correct 70 ms 23540 KB Output is correct
35 Correct 263 ms 31436 KB Output is correct
36 Runtime error 334 ms 262144 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -