結果
問題 | No.949 飲酒プログラミングコンテスト |
ユーザー |
![]() |
提出日時 | 2019-12-12 01:06:02 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 377 ms / 2,500 ms |
コード長 | 1,474 bytes |
コンパイル時間 | 2,208 ms |
コンパイル使用メモリ | 78,056 KB |
実行使用メモリ | 128,284 KB |
最終ジャッジ日時 | 2024-06-24 08:13:48 |
合計ジャッジ時間 | 9,714 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] a = new int[n + 1]; int[] b = new int[n + 1]; int[] d = new int[n + 1]; String[] sa = br.readLine().split(" "); for (int i = 0; i <= n; i++) { a[i] = Integer.parseInt(sa[i]); } sa = br.readLine().split(" "); for (int i = 0; i <= n; i++) { b[i] = Integer.parseInt(sa[i]); } sa = br.readLine().split(" "); d[0] = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { d[i + 1] = Integer.parseInt(sa[i]); } br.close(); Arrays.sort(d); int[][] c = new int[n + 2][n + 2]; for (int i = 0; i <= n; i++) { int idx = n; for (int j = 0; j <= n; j++) { int sum = a[i] + b[j]; while (sum < d[idx]) { idx--; } c[i][j] = idx; } } int[][] dp = new int[n + 2][n + 2]; dp[0][0] = n + 1; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp[i + 1][j] = Math.min(c[i + 1][j], dp[i][j] - 1); int val = Math.min(c[i][j + 1], dp[i][j] - 1); dp[i][j + 1] = Math.max(dp[i][j + 1], val); } } dp[0][0] = 0; int ans = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { if (dp[i][j] > 0) { ans = Math.max(ans, i + j); } } } System.out.println(ans); } }