제출 #467825

#제출 시각아이디문제언어결과실행 시간메모리
467825rainliofficialKnapsack (NOI18_knapsack)Java
0 / 100
1065 ms8820 KiB
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++){ for (int k=1; 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 weight, int val, int k){ this.val = val; this.weight = weight; this.k = k; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...