oj.uz

Submission #550743

# Submission time Handle Problem Language Result Execution time Memory
550743 2022-04-19T01:27:45 Z PikaChu999 Knapsack (NOI18_knapsack) Java 11
100 / 100
 782 ms 73036 KB 
/*
15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1

value, weight, copies
*/
import java.util.*;
import java.io.*;

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

    StringTokenizer details = new StringTokenizer(br.readLine());
    int capacity = Integer.parseInt(details.nextToken()); //capacity of shopping basket
    int n = Integer.parseInt(details.nextToken()); //number of types of shopping items 
    ArrayList<Item>[] items = new ArrayList[capacity + 1]; //sorted by weight and then value (largest to smallest value)
    for(int a = 0; a <= capacity; a++) items[a] = new ArrayList<Item>();
    for(int a = 0; a < n; a++){
      StringTokenizer ite = new StringTokenizer(br.readLine()); //value, weight and copies
      long val = Long.parseLong(ite.nextToken());
      int weight = Integer.parseInt(ite.nextToken());
      int copies = Integer.parseInt(ite.nextToken());
      items[weight].add(new Item(val, copies));
    }
    for(int a = 0; a <= capacity; a++) Collections.sort(items[a]);
    //System.out.println(Arrays.toString(items));

    long[][] dp = new long[capacity + 1][capacity + 1]; //dp[a][b], where dp[a][b] is the max value that you can get given a capacity of i and all items with weight b or less     
    for(long[] row : dp) Arrays.fill(row, -1000000000000000L);
    dp[0][0] = 0; 
    long max = 0; 
    for(int maxWeight = 1; maxWeight <= capacity; maxWeight++){
      for(int cp = 0; cp <= capacity; cp++){
        long sm = 0; 
        int capacityTaken = 0; 
        dp[maxWeight][cp] = dp[maxWeight - 1][cp];
        for(Item i : items[maxWeight]){
          for(int cur = 0; cur < i.copies; cur++){
            capacityTaken += maxWeight; 
            sm += i.value;
            if(capacityTaken > cp) break; 
            dp[maxWeight][cp] = Math.max(dp[maxWeight][cp], dp[maxWeight - 1][cp - capacityTaken] + sm);
          }
          if(capacityTaken > cp) break; 
        }
        max = Math.max(max, dp[maxWeight][cp]);
      }
    }
    System.out.println(max);
    br.close();
  }
}
class Item implements Comparable<Item>{
  long value; 
  int copies; 
  public Item(long v, int c){
    value = v; 
    copies = c; 
  }
  public String toString(){
    return value + " " + copies; 
  }
  public int compareTo(Item i){
    if(i.value > value) return 1; 
    if(i.value < value) return -1; 
    return copies - i.copies; 
  }
}

Compilation message

Note: knapsack.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 24100 KB Output is correct
2 Correct 110 ms 23408 KB Output is correct
3 Correct 120 ms 23140 KB Output is correct
4 Correct 152 ms 23884 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8588 KB Output is correct
2 Correct 169 ms 51912 KB Output is correct
3 Correct 192 ms 51616 KB Output is correct
4 Correct 172 ms 51968 KB Output is correct
5 Correct 156 ms 52068 KB Output is correct
6 Correct 170 ms 51880 KB Output is correct
7 Correct 151 ms 51464 KB Output is correct
8 Correct 149 ms 51752 KB Output is correct
9 Correct 176 ms 51528 KB Output is correct
10 Correct 156 ms 51712 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8588 KB Output is correct
2 Correct 169 ms 51912 KB Output is correct
3 Correct 192 ms 51616 KB Output is correct
4 Correct 172 ms 51968 KB Output is correct
5 Correct 156 ms 52068 KB Output is correct
6 Correct 170 ms 51880 KB Output is correct
7 Correct 151 ms 51464 KB Output is correct
8 Correct 149 ms 51752 KB Output is correct
9 Correct 176 ms 51528 KB Output is correct
10 Correct 156 ms 51712 KB Output is correct
11 Correct 64 ms 8456 KB Output is correct
12 Correct 211 ms 51992 KB Output is correct
13 Correct 178 ms 51540 KB Output is correct
14 Correct 159 ms 52396 KB Output is correct
15 Correct 159 ms 52144 KB Output is correct
16 Correct 188 ms 63212 KB Output is correct
17 Correct 141 ms 51752 KB Output is correct
18 Correct 162 ms 51536 KB Output is correct
19 Correct 184 ms 51788 KB Output is correct
20 Correct 152 ms 51580 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 24100 KB Output is correct
2 Correct 110 ms 23408 KB Output is correct
3 Correct 120 ms 23140 KB Output is correct
4 Correct 152 ms 23884 KB Output is correct
5 Correct 68 ms 8588 KB Output is correct
6 Correct 169 ms 51912 KB Output is correct
7 Correct 192 ms 51616 KB Output is correct
8 Correct 172 ms 51968 KB Output is correct
9 Correct 156 ms 52068 KB Output is correct
10 Correct 170 ms 51880 KB Output is correct
11 Correct 151 ms 51464 KB Output is correct
12 Correct 149 ms 51752 KB Output is correct
13 Correct 176 ms 51528 KB Output is correct
14 Correct 156 ms 51712 KB Output is correct
15 Correct 64 ms 8456 KB Output is correct
16 Correct 211 ms 51992 KB Output is correct
17 Correct 178 ms 51540 KB Output is correct
18 Correct 159 ms 52396 KB Output is correct
19 Correct 159 ms 52144 KB Output is correct
20 Correct 188 ms 63212 KB Output is correct
21 Correct 141 ms 51752 KB Output is correct
22 Correct 162 ms 51536 KB Output is correct
23 Correct 184 ms 51788 KB Output is correct
24 Correct 152 ms 51580 KB Output is correct
25 Correct 69 ms 8420 KB Output is correct
26 Correct 165 ms 51572 KB Output is correct
27 Correct 185 ms 51848 KB Output is correct
28 Correct 154 ms 52112 KB Output is correct
29 Correct 167 ms 51852 KB Output is correct
30 Correct 213 ms 63252 KB Output is correct
31 Correct 140 ms 51560 KB Output is correct
32 Correct 160 ms 51532 KB Output is correct
33 Correct 189 ms 63136 KB Output is correct
34 Correct 198 ms 63552 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 24100 KB Output is correct
2 Correct 110 ms 23408 KB Output is correct
3 Correct 120 ms 23140 KB Output is correct
4 Correct 152 ms 23884 KB Output is correct
5 Correct 68 ms 8588 KB Output is correct
6 Correct 169 ms 51912 KB Output is correct
7 Correct 192 ms 51616 KB Output is correct
8 Correct 172 ms 51968 KB Output is correct
9 Correct 156 ms 52068 KB Output is correct
10 Correct 170 ms 51880 KB Output is correct
11 Correct 151 ms 51464 KB Output is correct
12 Correct 149 ms 51752 KB Output is correct
13 Correct 176 ms 51528 KB Output is correct
14 Correct 156 ms 51712 KB Output is correct
15 Correct 64 ms 8456 KB Output is correct
16 Correct 211 ms 51992 KB Output is correct
17 Correct 178 ms 51540 KB Output is correct
18 Correct 159 ms 52396 KB Output is correct
19 Correct 159 ms 52144 KB Output is correct
20 Correct 188 ms 63212 KB Output is correct
21 Correct 141 ms 51752 KB Output is correct
22 Correct 162 ms 51536 KB Output is correct
23 Correct 184 ms 51788 KB Output is correct
24 Correct 152 ms 51580 KB Output is correct
25 Correct 69 ms 8420 KB Output is correct
26 Correct 165 ms 51572 KB Output is correct
27 Correct 185 ms 51848 KB Output is correct
28 Correct 154 ms 52112 KB Output is correct
29 Correct 167 ms 51852 KB Output is correct
30 Correct 213 ms 63252 KB Output is correct
31 Correct 140 ms 51560 KB Output is correct
32 Correct 160 ms 51532 KB Output is correct
33 Correct 189 ms 63136 KB Output is correct
34 Correct 198 ms 63552 KB Output is correct
35 Correct 495 ms 18812 KB Output is correct
36 Correct 613 ms 48896 KB Output is correct
37 Correct 604 ms 48804 KB Output is correct
38 Correct 598 ms 49680 KB Output is correct
39 Correct 591 ms 53212 KB Output is correct
40 Correct 675 ms 72728 KB Output is correct
41 Correct 705 ms 71832 KB Output is correct
42 Correct 707 ms 71744 KB Output is correct
43 Correct 765 ms 71972 KB Output is correct
44 Correct 782 ms 71840 KB Output is correct
45 Correct 580 ms 72488 KB Output is correct
46 Correct 585 ms 53004 KB Output is correct
47 Correct 782 ms 73036 KB Output is correct
48 Correct 764 ms 72828 KB Output is correct
49 Correct 670 ms 51912 KB Output is correct
50 Correct 595 ms 61156 KB Output is correct