| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 486544 | john256 | Cloud Computing (CEOI18_clo) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.io.*;
import java.util.*;
public class clo {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
ArrayList<int[]> logs = new ArrayList<>();
for (int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
logs.add(new int[]{0, 0, 0});
logs.get(i)[0] = Integer.parseInt(st.nextToken());
logs.get(i)[1] = Integer.parseInt(st.nextToken());
logs.get(i)[2] = -Integer.parseInt(st.nextToken());
}
int m = Integer.parseInt(br.readLine());
for (int i=N; i<m+N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
logs.add(new int[]{0, 0, 0});
logs.get(i)[0] = -Integer.parseInt(st.nextToken());
logs.get(i)[1] = Integer.parseInt(st.nextToken());
logs.get(i)[2] = Integer.parseInt(st.nextToken());
}
Collections.sort(logs, (x, y) -> y[1]-x[1]);
long[][] dp = new long[2][100001];
Arrays.fill(dp[1], Long.MIN_VALUE);
dp[1][0] = 0;
for (int i=0; i<N+m; i++) {
dp[i%2] = dp[1-i%2].clone();
for (int c=0; c<=100000; c++) {
if (c-logs.get(i)[0]<0 || c-logs.get(i)[0]>100000 ||
dp[1-i%2][c-logs.get(i)[0]]==Long.MIN_VALUE) continue;
dp[i%2][c] = Math.max(dp[i%2][c], dp[1-i%2][c-logs.get(i)[0]] + logs.get(i)[2]);
}
}
long ans = -1;
for (int i=0; i<=100000; i++)
ans = Math.max(ans, dp[(N+m-1)%2][i]);
System.out.println(ans);
}
}