| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 803006 | procodgok | Knapsack (NOI18_knapsack) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
package knapsack;
import java.util.*;
public class KnapsackWeightedFrequency {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m=in.nextInt(), n=in.nextInt();
long[] a = new long[n];
long[] w = new long[n];
long[] freq = new long[n];
HashMap<Long, ArrayList<long[]>> pairs = new HashMap<>(); //(weight, {value, frequency})
for(int i=0; i<n; i++) {
a[i]=in.nextLong();
w[i]=in.nextLong();
freq[i]=in.nextLong();
}
for(int i=0; i<n; i++) {
if(pairs.containsKey(w[i])) {
pairs.get(w[i]).add(new long[] {a[i], freq[i]});
}
else {
pairs.put(w[i], new ArrayList<>(Arrays.asList(new long[] {a[i], freq[i]})));
}
}
long[] dp = new long[m+1];
for(int i=0; i<m+1; i++) {
dp[i]=-1;
}
dp[0]=0;
for(long weight : pairs.keySet()) {
ArrayList<long[]> curr = pairs.get(weight);
curr.sort(Comparator.comparingLong(b -> b[b.length-1]));
}
for(long weight : pairs.keySet()) {
long sum=0;
for(long[] j : pairs.get(weight)) {
sum += j[1];
}
for(int i=m; i>=weight; i--) {
long f = (long)(i/weight);
if(dp[i-(int)(Math.min(f, sum)*weight)]!=-1) {
long c = dp[i-(int)(Math.min(f, sum)*weight)];
for(long[] j : pairs.get(weight)) {
long fr = j[1], val = j[0];
if(fr>f) {
c += f*val;
f=0;
break;
}
else {
c += fr*val;
f -= fr;
}
}
dp[i] = Math.max(dp[i], c);
}
}
}
long max=0;
for(int i=0; i<m+1; i++) {
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
}