oj.uz

Submission #469428

# Submission time Handle Problem Language Result Execution time Memory
469428 2021-09-01T01:03:56 Z ImaginaryIQ Knapsack (NOI18_knapsack) Java 11
37 / 100
 197 ms 14060 KB 
import java.util.*;
import java.io.*;

public class knapsack {

    static int s, n;
    static int [][] arr;
    static int [][] dp; // dp[i][j][k] = the maximmum amount of value that we can using the first i items,
    // without exceeding weight j, while picking a max of k times
    public static void main(String[] args) throws Exception {
        Scanner io = new Scanner(System.in);
        s = io.nextInt();
        n = io.nextInt();

        arr = new int[n+1][3]; // v, w, count
        dp = new int[n+1][s+1];

        for (int i = 1; i <= n; i++) {
            arr[i][0] = io.nextInt(); // value, weight, and, number of picks
            arr[i][1] = io.nextInt();
            arr[i][2] = io.nextInt();
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= s; j++) {
                dp[i][j] = dp[i-1][j];

                // go back the number of times taken
                for (int k = 1; k <= Math.min(arr[i][2], n); k++) {
                    int prev = j - (arr[i][1] * k);
                    if (prev >= 0) {
                        dp[i][j] = Math.max(dp[i-1][prev] + arr[i][0] * k, dp[i][j]);
                    }
                }
            }
        }

        System.out.println(dp[n][s]);
        io.close();
    }

    static class pair implements Comparable<pair>{
        int p1, p2;
        public pair(int p1, int p2){
            this.p1 = p1;
            this.p2 = p2;
        }

        @Override
        public int compareTo(pair o) {
            return Integer.compare(this.p1, o.p1);
        }
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 10164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 11008 KB Output is correct
2 Correct 174 ms 13820 KB Output is correct
3 Correct 173 ms 13588 KB Output is correct
4 Correct 172 ms 13932 KB Output is correct
5 Correct 176 ms 13576 KB Output is correct
6 Correct 173 ms 13508 KB Output is correct
7 Correct 177 ms 13804 KB Output is correct
8 Correct 173 ms 13784 KB Output is correct
9 Correct 174 ms 13532 KB Output is correct
10 Correct 173 ms 14060 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 11008 KB Output is correct
2 Correct 174 ms 13820 KB Output is correct
3 Correct 173 ms 13588 KB Output is correct
4 Correct 172 ms 13932 KB Output is correct
5 Correct 176 ms 13576 KB Output is correct
6 Correct 173 ms 13508 KB Output is correct
7 Correct 177 ms 13804 KB Output is correct
8 Correct 173 ms 13784 KB Output is correct
9 Correct 174 ms 13532 KB Output is correct
10 Correct 173 ms 14060 KB Output is correct
11 Correct 154 ms 10872 KB Output is correct
12 Correct 197 ms 13700 KB Output is correct
13 Correct 175 ms 13740 KB Output is correct
14 Correct 179 ms 13880 KB Output is correct
15 Correct 180 ms 13644 KB Output is correct
16 Correct 173 ms 13824 KB Output is correct
17 Correct 184 ms 13676 KB Output is correct
18 Correct 174 ms 13772 KB Output is correct
19 Correct 178 ms 13648 KB Output is correct
20 Correct 179 ms 13524 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 10164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 10164 KB Output isn't correct
2 Halted 0 ms 0 KB -