結果

問題 No.3302 Sense Battle
コンテスト
ユーザー さかさのさかな
提出日時 2025-10-25 18:14:37
言語 Java
(openjdk 23)
結果
AC  
実行時間 990 ms / 2,000 ms
コード長 1,090 bytes
コンパイル時間 3,005 ms
コンパイル使用メモリ 80,016 KB
実行使用メモリ 247,040 KB
最終ジャッジ日時 2025-10-25 18:14:56
合計ジャッジ時間 18,630 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no3302_sense_battle;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//これ以降攻撃する回数がi回であると決定されている時、j回目の選択の直前からスタートするときの最大ダメージ
		long[][] dp = new long[n + 1][n + 1];
		long[] a = new long[n];
		long[] b = new long[n];
		for(int i = 0;i < n;i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
		}for(int i = 0;i <= n;i++) {
			for(int j = 0;j <= n;j++) {
				dp[i][j] = -1;
			}
		}dp[0][n] = 0;
		for(int i = n - 1;i >= 0;i--) {
			for(int j = 0;j < n - i;j++) {
				//攻撃する
				if(dp[j][i + 1] != -1) {
					dp[j + 1][i] = Math.max(dp[j + 1][i], dp[j][i + 1] + b[i]);
				}
				//ためる
				if(dp[j][i + 1] != -1) {
					dp[j][i] = Math.max(dp[j][i], dp[j][i + 1] +(long) j * a[i]);
				}
			}
		}long ans = -1;
		for(int i = 0;i <= n;i++) {
			ans = Math.max(ans, dp[i][0]);
		}System.out.print(ans);
		
		
	}

}
0