結果
問題 |
No.45 回転寿司
|
ユーザー |
|
提出日時 | 2020-10-08 16:40:33 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,763 bytes |
コンパイル時間 | 15,938 ms |
コンパイル使用メモリ | 377,440 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 05:58:06 |
合計ジャッジ時間 | 15,357 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
use std::io::{stdin, Read, StdinLock}; use std::str::FromStr; struct Input { n: usize, v: Vec<usize>, } fn read_input(cin_lock: &mut StdinLock) -> Input { let n = next_token(cin_lock); let v = (0..n).map(|_| next_token(cin_lock)).collect(); Input { n, v } } fn solve(input: Input) -> usize { let mut dp = vec![0; input.n]; for i in 0..input.n { dp[i] = dp[i] + input.v[i]; for j in i + 2..input.n { dp[j] = dp[i].max(dp[j]); } } return dp.into_iter().fold(0, usize::max); } #[cfg(test)] mod tests { use super::*; #[test] fn test_solve() { assert_eq!( solve(Input { n: 4, v: vec![1, 2, 3, 4] }), 6 ); assert_eq!( solve(Input { n: 4, v: vec![5, 4, 4, 9] }), 14 ); assert_eq!( solve(Input { n: 7, v: vec![1, 2, 9, 10, 1, 1, 4] }), 16 ); assert_eq!(solve(Input { n: 1, v: vec![100] }), 100); assert_eq!( solve(Input { n: 3, v: vec![1, 100, 1] }), 100, ); } } fn next_token<T: FromStr>(cin_lock: &mut StdinLock) -> T { cin_lock .by_ref() .bytes() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::<String>() .parse::<T>() .ok() .unwrap() } fn main() { let cin = stdin(); let mut cin_lock = cin.lock(); let input = read_input(&mut cin_lock); println!("{}", solve(input)); }