oj.uz

Submission #467826

# Submission time Handle Problem Language Result Execution time Memory
467826 2021-08-24T21:11:15 Z rainliofficial Knapsack (NOI18_knapsack) Java 11
73 / 100
 936 ms 262148 KB 
import java.io.*;
import java.util.*;

public class knapsack {
    static int maxW, n;
    static Item[] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader file = new BufferedReader(new FileReader("file.in"));
        StringTokenizer st = new StringTokenizer(file.readLine());
        maxW = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new Item[n];
        for (int i=0; i<n; i++){
            st = new StringTokenizer(file.readLine());
            arr[i] = new Item(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        long[][] dp = new long[maxW+1][n+1];
        for (int i=1; i<=maxW; i++){
            for (int j=1; j<=n; j++){
                dp[i][j] = dp[i][j-1];
                for (int k=1; arr[j-1].weight*k<=i && k <= arr[j-1].k; k++){
                    if (i >= (long)arr[j-1].weight*k){
                        dp[i][j] = Math.max(dp[i][j], dp[i-arr[j-1].weight*k][j-1] + (long)arr[j-1].val*k);
                    }
                }
            }
        }
        System.out.println(dp[maxW][n]);
    }
    static class Item{
        int val, weight, k;
        public Item(int val, int weight, int k){
            this.val = val;
            this.weight = weight;
            this.k = k;
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8128 KB Output is correct
2 Correct 69 ms 8288 KB Output is correct
3 Correct 94 ms 9084 KB Output is correct
4 Correct 70 ms 8516 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8404 KB Output is correct
2 Correct 96 ms 12288 KB Output is correct
3 Correct 111 ms 12248 KB Output is correct
4 Correct 86 ms 12308 KB Output is correct
5 Correct 88 ms 12332 KB Output is correct
6 Correct 91 ms 12692 KB Output is correct
7 Correct 100 ms 12556 KB Output is correct
8 Correct 86 ms 12408 KB Output is correct
9 Correct 90 ms 12584 KB Output is correct
10 Correct 95 ms 12360 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8404 KB Output is correct
2 Correct 96 ms 12288 KB Output is correct
3 Correct 111 ms 12248 KB Output is correct
4 Correct 86 ms 12308 KB Output is correct
5 Correct 88 ms 12332 KB Output is correct
6 Correct 91 ms 12692 KB Output is correct
7 Correct 100 ms 12556 KB Output is correct
8 Correct 86 ms 12408 KB Output is correct
9 Correct 90 ms 12584 KB Output is correct
10 Correct 95 ms 12360 KB Output is correct
11 Correct 74 ms 8516 KB Output is correct
12 Correct 106 ms 12676 KB Output is correct
13 Correct 95 ms 12544 KB Output is correct
14 Correct 87 ms 12244 KB Output is correct
15 Correct 88 ms 12312 KB Output is correct
16 Correct 91 ms 12588 KB Output is correct
17 Correct 89 ms 12472 KB Output is correct
18 Correct 88 ms 12608 KB Output is correct
19 Correct 91 ms 12468 KB Output is correct
20 Correct 97 ms 12440 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8128 KB Output is correct
2 Correct 69 ms 8288 KB Output is correct
3 Correct 94 ms 9084 KB Output is correct
4 Correct 70 ms 8516 KB Output is correct
5 Correct 75 ms 8404 KB Output is correct
6 Correct 96 ms 12288 KB Output is correct
7 Correct 111 ms 12248 KB Output is correct
8 Correct 86 ms 12308 KB Output is correct
9 Correct 88 ms 12332 KB Output is correct
10 Correct 91 ms 12692 KB Output is correct
11 Correct 100 ms 12556 KB Output is correct
12 Correct 86 ms 12408 KB Output is correct
13 Correct 90 ms 12584 KB Output is correct
14 Correct 95 ms 12360 KB Output is correct
15 Correct 74 ms 8516 KB Output is correct
16 Correct 106 ms 12676 KB Output is correct
17 Correct 95 ms 12544 KB Output is correct
18 Correct 87 ms 12244 KB Output is correct
19 Correct 88 ms 12312 KB Output is correct
20 Correct 91 ms 12588 KB Output is correct
21 Correct 89 ms 12472 KB Output is correct
22 Correct 88 ms 12608 KB Output is correct
23 Correct 91 ms 12468 KB Output is correct
24 Correct 97 ms 12440 KB Output is correct
25 Correct 76 ms 8236 KB Output is correct
26 Correct 936 ms 12736 KB Output is correct
27 Correct 96 ms 12468 KB Output is correct
28 Correct 84 ms 12332 KB Output is correct
29 Correct 85 ms 12200 KB Output is correct
30 Correct 95 ms 12596 KB Output is correct
31 Correct 89 ms 12296 KB Output is correct
32 Correct 98 ms 12768 KB Output is correct
33 Correct 114 ms 12464 KB Output is correct
34 Correct 95 ms 12428 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 8128 KB Output is correct
2 Correct 69 ms 8288 KB Output is correct
3 Correct 94 ms 9084 KB Output is correct
4 Correct 70 ms 8516 KB Output is correct
5 Correct 75 ms 8404 KB Output is correct
6 Correct 96 ms 12288 KB Output is correct
7 Correct 111 ms 12248 KB Output is correct
8 Correct 86 ms 12308 KB Output is correct
9 Correct 88 ms 12332 KB Output is correct
10 Correct 91 ms 12692 KB Output is correct
11 Correct 100 ms 12556 KB Output is correct
12 Correct 86 ms 12408 KB Output is correct
13 Correct 90 ms 12584 KB Output is correct
14 Correct 95 ms 12360 KB Output is correct
15 Correct 74 ms 8516 KB Output is correct
16 Correct 106 ms 12676 KB Output is correct
17 Correct 95 ms 12544 KB Output is correct
18 Correct 87 ms 12244 KB Output is correct
19 Correct 88 ms 12312 KB Output is correct
20 Correct 91 ms 12588 KB Output is correct
21 Correct 89 ms 12472 KB Output is correct
22 Correct 88 ms 12608 KB Output is correct
23 Correct 91 ms 12468 KB Output is correct
24 Correct 97 ms 12440 KB Output is correct
25 Correct 76 ms 8236 KB Output is correct
26 Correct 936 ms 12736 KB Output is correct
27 Correct 96 ms 12468 KB Output is correct
28 Correct 84 ms 12332 KB Output is correct
29 Correct 85 ms 12200 KB Output is correct
30 Correct 95 ms 12596 KB Output is correct
31 Correct 89 ms 12296 KB Output is correct
32 Correct 98 ms 12768 KB Output is correct
33 Correct 114 ms 12464 KB Output is correct
34 Correct 95 ms 12428 KB Output is correct
35 Correct 397 ms 17772 KB Output is correct
36 Runtime error 491 ms 262148 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -