結果

問題 No.951 【本日限定】１枚頼むともう１枚無料！
ユーザー tenten
提出日時 2020-12-17 12:34:20
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 1,315 bytes
コンパイル時間 3,757 ms
コンパイル使用メモリ 77,740 KB
実行使用メモリ 532,400 KB
最終ジャッジ日時 2024-09-20 06:58:05
合計ジャッジ時間 12,362 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 MLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
    static int[][][] dp;
    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());
		}
		Arrays.sort(pizzas);
		dp = new int[n][k + 1][2];
		System.out.println(dfw(n - 1, k, 0));
	}
	
	static int dfw(int idx, int cost, int isFree) {
	    if (cost < 0) {
	        return Integer.MIN_VALUE;
	    }
	    if (idx < 0) {
	        return 0;
	    }
	    if (dp[idx][cost][isFree] == 0) {
	        if (isFree == 0) {
	            dp[idx][cost][isFree] = Math.max(dfw(idx - 1, cost, isFree), dfw(idx - 1, cost - pizzas[idx].price, 1) + pizzas[idx].delicious);
	        } else {
	            dp[idx][cost][isFree] = Math.max(dfw(idx - 1, cost, isFree), dfw(idx - 1, cost, 0) + pizzas[idx].delicious);
	        }
	    }
	    return dp[idx][cost][isFree];
	}
	
	static class Pizza implements Comparable<Pizza> {
	    int price;
	    int delicious;
	    
	    public Pizza(int price, int delicious) {
	        this.price = price;
	        this.delicious = delicious;
	    }
	    
	    public int compareTo(Pizza another) {
	        return price - another.price;
	    }
	}
}
0