結果

問題 No.974 最後の日までに
コンテスト
ユーザー htensai
提出日時 2020-01-26 08:45:30
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,211 bytes
コンパイル時間 2,295 ms
コンパイル使用メモリ 77,676 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-09-14 10:48:19
合計ジャッジ時間 9,739 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
    static long[] incomes;
    static long[] likes;
    static long[] costs;
    static HashMap<Long, Long>[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        incomes = new long[w + 1];
        likes = new long[w + 1];
        costs = new long[w + 1];
        dp = new HashMap[w + 1];
        for (int i = 1; i <= w; i++) {
            incomes[i] = sc.nextLong();
            likes[i] = sc.nextLong();
            costs[i] = sc.nextLong();
            dp[i] = new HashMap<Long, Long>();
        }
        
        System.out.println(dfw(w, 0));
    }
    
    static long dfw(int idx, long money) {
        if (idx == 0) {
            if (money > 0) {
                return Long.MIN_VALUE;
            } else {
                return 0;
            }
        }
        if (dp[idx].containsKey(money)) {
            return dp[idx].get(money);
        }
        long ans = dfw(idx - 1, money - incomes[idx]);
        if (idx >= 2) {
            ans = Math.max(ans, dfw(idx - 2, money + costs[idx]) + likes[idx]);
        }
        dp[idx].put(money, ans);
        return ans;
    }
    
}
0