結果
問題 | No.3014 岩井満足性問題 |
ユーザー |
![]() |
提出日時 | 2025-01-25 14:44:32 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 2,123 ms / 3,000 ms |
コード長 | 1,622 bytes |
コンパイル時間 | 3,176 ms |
コンパイル使用メモリ | 85,364 KB |
実行使用メモリ | 50,692 KB |
最終ジャッジ日時 | 2025-01-25 23:29:02 |
合計ジャッジ時間 | 25,580 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
import java.util.Scanner; public class Test { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long inf = (long) Math.pow(10, 16); int N = sc.nextInt(); int D = sc.nextInt(); int K = sc.nextInt(); int[] A = new int[N]; int[] C = new int[N]; for(int i = 0; i < N; ++i) { A[i] = sc.nextInt(); } for(int i = 0; i < N; ++i) { C[i] = sc.nextInt(); } sc.close(); long[][] dp = new long[D+1][K+1]; for(int d = 0; d <= D; ++d) { for(int k = 0; k <= K; ++k) { dp[d][k] = -inf; } } dp[0][0] = 0; for(int i = 0; i < N; ++i) { long[][] ndp = new long[D+1][K+1]; for(int d = 0; d <= D; ++d) { for(int k = 0; k <= K; ++k) { ndp[d][k] = dp[d][k]; } } for(int d = 0; d < D; ++d) { for(int k = 0; k <= K; ++k) { if (dp[d][k] == -inf) continue; int j = Integer.min(k+C[i], K); if(ndp[d+1][j] == -inf) { ndp[d+1][j] = dp[d][k]+A[i]; } else { ndp[d+1][j] = Long.max(ndp[d+1][j], dp[d][k]+A[i]); } } } dp = ndp; System.gc(); } if (dp[D][K] == -inf) { System.out.println("No"); } else { System.out.println(dp[D][K]); } } }