結果
問題 | No.2693 Sword |
ユーザー |
|
提出日時 | 2024-03-28 11:06:01 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 3,014 bytes |
コンパイル時間 | 13,092 ms |
コンパイル使用メモリ | 386,672 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-09-30 14:42:47 |
合計ジャッジ時間 | 13,601 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
static LIM: i64 = 1_000_000_000_000_000_000;fn main() {// inputlet mut sc = Scanner::new(std::io::stdin().lock());let n: usize = sc.next();let p: i64 = sc.next();let k: usize = sc.next();let tb: Vec<(u8, i64)> = (0..n).map(|_x| (sc.next::<u8>(), sc.next::<i64>())).collect();// answerlet ans = solve(n, p, k, tb).unwrap_or(-1);// outputfastout(&ans.to_string());}fn solve(n: usize, p: i64, k: usize, tb: Vec<(u8, i64)>) -> Option<i64> {let mut dp = vec![vec![-1; k + 1]; n + 1];dp[0][0] = p;for (i, &(t, b)) in tb.iter().enumerate() {for j in 0..=k {if dp[i][j] > 0 && dp.get(i + 1).is_some() {dp[i + 1][j] = dp[i + 1][j].max(dp[i][j]);if dp[i + 1].get(j + 1).is_some() {match t {1 => {dp[i + 1][j + 1] = dp[i][j] + b;}2 => {dp[i + 1][j + 1] = dp[i][j] * 2;}_ => unreachable!(),}if dp[i + 1][j + 1] > LIM {return None;}}}}}Some(dp[n][k])}// snippetstruct Scanner<R: std::io::BufRead> {reader: R,buf: Vec<u8>,pos: usize,}impl<R: std::io::BufRead> Scanner<R> {fn new(reader: R) -> Self {Scanner {reader,buf: Vec::new(),pos: 0,}}#[allow(dead_code)]fn with_capacity(reader: R, capacity: usize) -> Self {Scanner {reader,buf: Vec::with_capacity(capacity),pos: 0,}}fn next<T: std::str::FromStr>(&mut self) -> TwhereT::Err: std::fmt::Debug,{if self.buf.is_empty() {self.read_next_line();}let mut start = None;loop {if self.pos == self.buf.len() {break;}match (self.buf[self.pos], start.is_some()) {(b' ', true) | (b'\n', true) => break,(_, true) | (b' ', false) => self.pos += 1,(b'\n', false) => self.read_next_line(),(_, false) => start = Some(self.pos),}}let elem = unsafe { std::str::from_utf8_unchecked(&self.buf[start.unwrap()..self.pos]) };elem.parse().unwrap_or_else(|_| panic!("{}", format!("failed parsing: {}", elem)))}fn read_next_line(&mut self) {self.pos = 0;self.buf.clear();if self.reader.read_until(b'\n', &mut self.buf).unwrap() == 0 {panic!("Reached EOF");}}}fn fastout(s: &str) {use std::io::{stdout, BufWriter, Write};let mut out = BufWriter::new(stdout().lock());writeln!(out, "{}", s).expect("failed to write data.");}