結果

問題 No.3302 Sense Battle
ユーザー KA37RI
提出日時 2025-10-05 16:26:41
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 699 bytes
コンパイル時間 11,174 ms
コンパイル使用メモリ 398,196 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-05 16:26:58
合計ジャッジ時間 15,073 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 15 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #

use proconio::input;

fn solve() -> i64 {
  input! {
    n: usize,
    ab: [(i64, i64); n],
  }
  let mut table = vec![i64::MIN; n + 1];
  table[0] = 0;
  for &(ai, bi) in ab.iter() {
    let mut ntable = vec![i64::MIN; n + 1];
    let mut atable = table.clone();
    for i in 1..=n {
      atable[i] = atable[i-1].max(atable[i]);
    }
    for i in 0..=n {
      if table[i] < 0 {
        continue;
      }
      ntable[i.saturating_sub(1)] = table[i] + bi;
    }
    for i in 0..=n {
      if atable[i] < 0 {
        continue;
      }
      ntable[i] = ntable[i].max(atable[i] + ai * i as i64);
    }
    table = ntable;
  }
  table[0]
}

fn main() {
  let ans = solve();
  println!("{}", ans);
}
0