| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 842389 | space_man | Knapsack (NOI18_knapsack) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
import static java.lang.System.exit;
public class NOI18_knapsack {
static FastIO in;
static PrintWriter out;
static boolean multiTests = false;
static boolean fileIO = false;
void solve(int tNum) throws IOException {
int s = in.nextInt(), n = in.nextInt();
HashMap<Integer, ArrayList<Pair>> inventory = new HashMap<>();
for (int i = 0; i < n; i++) {
int v = in.nextInt(), w = in.nextInt(), c = in.nextInt();
if(!inventory.containsKey(w)) inventory.put(w, new ArrayList<>());
inventory.get(w).add(new Pair(v, c));
}
long[][] dp = new long[inventory.size() + 1][s + 1];
for (long[] longs : dp) {
Arrays.fill(longs, Integer.MIN_VALUE);
}
dp[0][0] = 0;
int id = 1;
for (Map.Entry<Integer, ArrayList<Pair>> entry : inventory.entrySet()) {
int w = entry.getKey();
ArrayList<Pair> list = entry.getValue();
list.sort(Comparator.comparingInt(p -> -p.cost));
for (int i = 0; i <= s; i++) {
dp[id][i] = dp[id - 1][i];
int taken = 0, index = 0, currTaken = 0;
long total = 0L;
while ((taken + 1) * w <= i && index < list.size()) {
taken++;
total += list.get(index).cost;
if(dp[id-1][i - w * taken] != Integer.MIN_VALUE) {
dp[id][i] = Math.max(dp[id][i], dp[id-1][i - w * taken] + total);
}
currTaken++;
if(currTaken == list.get(index).count) {
index++;
currTaken = 0;
}
}
}
id++;
}
long ans = Integer.MIN_VALUE;
for (int i = 0; i <= s; i++) {
ans = Math.max(ans, dp[inventory.size()][i]);
}
out.println(ans);
}
static class Pair {
int cost, count;
public Pair(int cost, int count) {
this.cost = cost;
this.count = count;
}
}
public static void main(String[] args) {
try {
in = fileIO ? new FastIO(".in") : new FastIO();
out = fileIO ? new PrintWriter(new BufferedWriter(new FileWriter(".out"))) : new PrintWriter(System.out);
NOI18_knapsack closing = new NOI18_knapsack();
int T = multiTests ? in.nextInt() : 1;
for (int t = 1; t <= T; t++) {
closing.solve(t);
}
in.close();
out.close();
} catch (IOException e) {
e.printStackTrace();
exit(1);
}
}
static class FastIO implements AutoCloseable {
private DataInputStream din;
private byte[] buffer;
private int pointer, bytesRead;
public FastIO() {
this(new DataInputStream(System.in));
}
public FastIO(String filename) throws FileNotFoundException {
this(new DataInputStream(new FileInputStream(filename)));
}
private FastIO(DataInputStream din) {
this.din = din;
buffer = new byte[1 << 17];
pointer = bytesRead = 0;
}
public int nextInt() throws IOException {
int r = 0;
byte b;
do {
b = nextByte();
} while (b <= ' ');
boolean negative = false;
if (b == '-') {
negative = true;
b = nextByte();
}
while (b >= '0' && b <= '9') {
r = 10 * r + b - '0';
b = nextByte();
}
return (negative) ? -r : r;
}
public long nextLong() throws IOException {
long r = 0;
byte b;
do {
b = nextByte();
} while (b <= ' ');
boolean negative = false;
if (b == '-') {
negative = true;
b = nextByte();
}
while (b >= '0' && b <= '9') {
r = 10 * r + b - '0';
b = nextByte();
}
return (negative) ? -r : r;
}
public double nextDouble() throws IOException {
double r = 0, d = 1;
byte b;
do {
b = nextByte();
} while (b <= ' ');
boolean negative = false;
if (b == '-') {
negative = true;
b = nextByte();
}
while (b >= '0' && b <= '9') {
r = 10 * r + b - '0';
b = nextByte();
}
if (b == '.') {
b = nextByte();
while (b >= '0' && b <= '9') {
r += (b - '0') / (d *= 10);
b = nextByte();
}
}
return (negative) ? -r : r;
}
public String next() throws IOException {
StringBuffer ret = new StringBuffer();
byte b;
do {
b = nextByte();
} while (b <= ' ');
while (b > ' ') {
ret.appendCodePoint(b);
b = nextByte();
}
return ret.toString();
}
public byte nextByte() throws IOException {
if (pointer == bytesRead) {
bytesRead = din.read(buffer, 0, buffer.length);
pointer = 0;
}
return buffer[pointer++];
}
@Override
public void close() throws IOException {
if (din == null) {
return;
}
din.close();
}
}
}