제출 #1237270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237270		kamran0708	Knapsack (NOI18_knapsack)	Java	37 / 100	222 ms	327680 KiB

knapsack

import java.util.*;
public class knapsack {

    public static int [][][] dp  ;

    public static int solve(int [][] store,int s, int currWt, int idx, int used){

        if(idx >= store.length || currWt > s) return Integer.MIN_VALUE ;
        if(dp[idx][currWt][used] != -1)return dp[idx][currWt][used] ;

        //Pick
        int pick1 = 0 ;
       
        if(store[idx][1] + currWt <= s && store[idx][2] > used){
            
            pick1 = store[idx][0] + solve(store, s, currWt+store[idx][1], idx, used+1) ;

            
        }
        int notPick = solve(store, s, currWt, idx+1,0) ;

        return dp[idx][currWt][used]  = Math.max(pick1,notPick) ;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in) ;
        int s = sc.nextInt() ;
        int n = sc.nextInt() ;
        int [][] store = new int [n][3] ;
        int maxK = -1 ;
        for(int i=0 ;i <n ;i++){
            store[i][0] = sc.nextInt() ;
            store[i][1] = sc.nextInt() ;
            store[i][2] = sc.nextInt() ;
            maxK = Math.max(maxK,store[i][2]) ;
        }
        dp = new int [n][s+1][maxK+1] ;

        for(int [][] arr2 : dp){
            for(int [] arr3 : arr2){
                  Arrays.fill(arr3,-1) ;
            }
        }

        System.out.println(solve(store, s, 0, 0,0));


    }
}

• Subtask 1: 0 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27