結果
問題 | No.54 Happy Hallowe'en |
ユーザー |
![]() |
提出日時 | 2021-03-03 19:59:59 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,365 bytes |
コンパイル時間 | 3,077 ms |
コンパイル使用メモリ | 77,648 KB |
実行使用メモリ | 443,040 KB |
最終ジャッジ日時 | 2024-10-03 08:46:30 |
合計ジャッジ時間 | 31,168 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 13 TLE * 1 -- * 5 |
ソースコード
import java.util.*;public class Main {static House[] houses;static int[][] dp;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();houses = new House[n];for (int i = 0; i < n; i++) {houses[i] = new House(sc.nextInt(), sc.nextInt());}Arrays.sort(houses);dp = new int[n][10001];for (int[] arr : dp) {Arrays.fill(arr, -1);}System.out.println(dfw(n - 1, 0));}static int dfw(int idx, int value) {if (idx < 0) {return 0;}if (value > 10000) {return 0;}if (dp[idx][value] < 0) {dp[idx][value] = dfw(idx - 1, value);if (houses[idx].limit > value) {dp[idx][value] = Math.max(dp[idx][value], dfw(idx - 1, value + houses[idx].gain) + houses[idx].gain);}}return dp[idx][value];}static class House implements Comparable<House> {int gain;int limit;public House(int gain, int limit) {this.gain = gain;this.limit = limit;}public int compareTo(House another) {return another.limit + another.gain - limit - gain;}}}