結果

問題 No.3302 Sense Battle
コンテスト
ユーザー さかさのさかな
提出日時 2025-10-25 18:14:37
言語 Java
(openjdk 25.0.2)
コンパイル:
javac -encoding UTF8 _filename_
実行:
java -ea -Xmx700m -Xss256M -DONLINE_JUDGE=true _class_
結果
AC  
実行時間 559 ms / 2,000 ms
+ 715µs
コード長 1,090 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,366 ms
コンパイル使用メモリ 83,860 KB
実行使用メモリ 263,352 KB
最終ジャッジ日時 2026-07-16 00:27:56
合計ジャッジ時間 11,358 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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