結果

問題 No.37 遊園地のアトラクション
ユーザー tentententen
提出日時 2020-10-23 09:00:05
言語 Java
(openjdk 23)
結果
AC  
実行時間 166 ms / 5,000 ms
コード長 1,289 bytes
コンパイル時間 2,729 ms
コンパイル使用メモリ 77,256 KB
実行使用メモリ 42,044 KB
最終ジャッジ日時 2024-10-10 13:44:29
合計ジャッジ時間 8,186 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.*;
public class Main {
static int[] costs;
static int[] values;
static int[][] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int n = sc.nextInt();
costs = new int[n];
for (int i = 0; i < n; i++) {
costs[i] = sc.nextInt();
}
values = new int[n];
for (int i = 0; i < n; i++) {
values[i] = sc.nextInt();
}
dp = new int[n][t + 1];
for (int[] arr : dp) {
Arrays.fill(arr, -1);
}
System.out.println(dfw(n - 1, t));
}
static int dfw(int idx, int time) {
if (time < 0) {
return Integer.MIN_VALUE;
}
if (idx < 0) {
return 0;
}
if (dp[idx][time] < 0) {
int v = values[idx];
int t = time;
int sum = 0;
while (t >= 0) {
dp[idx][time] = Math.max(dp[idx][time], dfw(idx - 1, t) + sum);
if (v == 0) {
break;
}
sum += v;
v /= 2;
t -= costs[idx];
}
}
return dp[idx][time];
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0