oj.uz

Submission #469994

# Submission time Handle Problem Language Result Execution time Memory
469994 2021-09-02T13:50:45 Z ImaginaryIQ Knapsack (NOI18_knapsack) Java 11
37 / 100
 221 ms 14324 KB 
import java.util.*;
import java.io.*;

public class knapsack {

    static int s, n;
    static long [][] arr;
    static long [][] 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 long[n+1][3]; // v, w, count
        dp = new long[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();
        }

        dp [0][0] = 0;
        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++) {
                    long prev = j - (arr[i][1] * k);
                    if (prev >= 0) {
                        dp[i][j] = Math.max(dp[i-1][(int)prev] + arr[i][0] * k, dp[i][j]);
                    }
                }
            }
        }

        long ans = 0;
        for (int i = 0; i <= s; i++) {
            ans = Math.max(dp[n][i], ans);
        }
        
        System.out.println(ans);
        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 120 ms 10144 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 156 ms 11160 KB Output is correct
2 Correct 192 ms 13936 KB Output is correct
3 Correct 177 ms 13900 KB Output is correct
4 Correct 180 ms 14284 KB Output is correct
5 Correct 187 ms 14256 KB Output is correct
6 Correct 177 ms 13964 KB Output is correct
7 Correct 188 ms 14036 KB Output is correct
8 Correct 184 ms 14324 KB Output is correct
9 Correct 181 ms 14012 KB Output is correct
10 Correct 183 ms 14168 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 11160 KB Output is correct
2 Correct 192 ms 13936 KB Output is correct
3 Correct 177 ms 13900 KB Output is correct
4 Correct 180 ms 14284 KB Output is correct
5 Correct 187 ms 14256 KB Output is correct
6 Correct 177 ms 13964 KB Output is correct
7 Correct 188 ms 14036 KB Output is correct
8 Correct 184 ms 14324 KB Output is correct
9 Correct 181 ms 14012 KB Output is correct
10 Correct 183 ms 14168 KB Output is correct
11 Correct 154 ms 11048 KB Output is correct
12 Correct 221 ms 14224 KB Output is correct
13 Correct 184 ms 14032 KB Output is correct
14 Correct 184 ms 14272 KB Output is correct
15 Correct 181 ms 14144 KB Output is correct
16 Correct 181 ms 13988 KB Output is correct
17 Correct 183 ms 14024 KB Output is correct
18 Correct 183 ms 13932 KB Output is correct
19 Correct 184 ms 14044 KB Output is correct
20 Correct 184 ms 13964 KB Output is correct

Subtask #4
0 / 24.0

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

Subtask #5
0 / 27.0

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