結果

問題 No.951 【本日限定】１枚頼むともう１枚無料！
コンテスト
ユーザー tenten
提出日時 2021-03-11 09:50:20
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 1,735 bytes
コンパイル時間 2,496 ms
コンパイル使用メモリ 79,752 KB
実行使用メモリ 514,896 KB
最終ジャッジ日時 2024-10-12 23:49:36
合計ジャッジ時間 10,170 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 MLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
    static ArrayList<HashMap<Integer, Integer>> paid = new ArrayList<>();
    static ArrayList<HashMap<Integer, Integer>> free = new ArrayList<>();
    static Pizza[] pizzas;
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		pizzas = new Pizza[n];
		for (int i = 0; i < n; i++) {
		    pizzas[i] = new Pizza(sc.nextInt(), sc.nextInt());
		    paid.add(new HashMap<>());
		    free.add(new HashMap<>());
		}
		Arrays.sort(pizzas);
		System.out.println(dfw(n - 1, k, true));
   }
   
   static class Pizza implements Comparable<Pizza> {
       int price;
       int value;
       
       public Pizza(int price, int value) {
           this.price = price;
           this.value = value;
       }
       
       public int compareTo(Pizza another) {
           return price - another.price;
       }
   }
   
   static int dfw(int idx, int cost, boolean isPaid) {
       if (cost < 0) {
           return Integer.MIN_VALUE;
       }
       if (idx < 0) {
           return 0;
       }
       if (isPaid) {
           if (paid.get(idx).containsKey(cost)) {
               return paid.get(idx).get(cost);
           }
           int ans = Math.max(dfw(idx - 1, cost, true), dfw(idx - 1, cost - pizzas[idx].price, false) + pizzas[idx].value);
           paid.get(idx).put(cost, ans);
           return ans;
       } else {
           if (free.get(idx).containsKey(cost)) {
               return free.get(idx).get(cost);
           }
           int ans = Math.max(dfw(idx - 1, cost, true) + pizzas[idx].value, dfw(idx - 1, cost, false));
           free.get(idx).put(cost, ans);
           return ans;
       }
   }
}
0