제출 #1144973

#제출 시각아이디문제언어결과실행 시간메모리
1144973uranium235Knapsack (NOI18_knapsack)Java
73 / 100
1099 ms86184 KiB
//package ojuz; import java.io.*; import java.util.*; import java.util.stream.Collectors; public class knapsack { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String[] first = reader.readLine().split(" "); int s = Integer.parseInt(first[0]), n = Integer.parseInt(first[1]); List<int[]> items = new ArrayList<>(); for (int i = 0; i < n; i++) { String[] arr = reader.readLine().split(" "); int v = Integer.parseInt(arr[0]), w = Integer.parseInt(arr[1]), k = Integer.parseInt(arr[2]); k = Math.min(k, s / w); if (k == 1) { items.add(new int[] {v, w}); continue; } int log = 31 - Integer.numberOfLeadingZeros(k); for (int j = 0; j < log; j++) { // System.out.println(log); items.add(new int[] {v << j, w << j}); } int mult = k - (1 << log) + 1; // System.out.println("mult: " + mult); items.add(new int[] {v * mult, w * mult}); } // System.out.println(items.stream().map(Arrays::toString).collect(Collectors.toList())); long[] dp = new long[s + 1]; for (int[] item : items) { for (int i = s; i >= item[1]; i--) { dp[i] = Math.max(dp[i], dp[i - item[1]] + item[0]); } } System.out.println(dp[s]); } }
#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...