結果
問題 | No.484 収穫 |
ユーザー | koba-e964 |
提出日時 | 2017-02-11 17:53:40 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,411 bytes |
コンパイル時間 | 19,354 ms |
コンパイル使用メモリ | 378,404 KB |
実行使用メモリ | 220,928 KB |
最終ジャッジ日時 | 2024-10-13 13:13:21 |
合計ジャッジ時間 | 26,486 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 5 ms
5,248 KB |
testcase_10 | AC | 4 ms
5,248 KB |
testcase_11 | AC | 5 ms
5,248 KB |
testcase_12 | AC | 536 ms
220,800 KB |
testcase_13 | AC | 531 ms
220,800 KB |
testcase_14 | AC | 542 ms
220,800 KB |
testcase_15 | AC | 533 ms
220,800 KB |
testcase_16 | AC | 527 ms
220,800 KB |
testcase_17 | AC | 526 ms
220,800 KB |
testcase_18 | AC | 564 ms
220,800 KB |
testcase_19 | AC | 531 ms
220,928 KB |
testcase_20 | AC | 532 ms
220,800 KB |
testcase_21 | AC | 524 ms
220,800 KB |
testcase_22 | AC | 534 ms
220,800 KB |
testcase_23 | WA | - |
ソースコード
#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::*; #[allow(dead_code)] fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).ok(); return ret; } fn get_word() -> String { let mut stdin = std::io::stdin(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec<u8> = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.unwrap_or(0) == 0 || u8b[0] <= b' ' { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = std::string::String::from_utf8(buf).unwrap(); return ret; } } } fn parse<T: std::str::FromStr>(s: &str) -> T { s.parse::<T>().ok().unwrap() } #[allow(dead_code)] fn get<T: std::str::FromStr>() -> T { parse(&get_word()) } const INF: i64 = 1 << 50; fn solve(a: &[i64]) -> i64 { let n = a.len(); if n == 1 { return a[0]; } let mut dp = vec![vec![vec![INF; 2]; n + 1]; n]; dp[1][n][0] = a[0]; dp[0][n - 1][1] = a[n - 1]; for s in (0 .. n - 1).rev() { for i in 0 .. min(n - s + 1, n) { // dp[i][i + s][0], goes to i - 1 let mut res = INF; if i >= 1 { res = min(res, dp[i - 1][i + s][1] + s as i64 + 1); } if i >= 2 { res = min(res, dp[i - 1][i + s][0] + 1); } if i >= 1 { res = max(res, a[i - 1]); } dp[i][i + s][0] = res; // dp[i][i + s][1], goes to i + s + 1 let mut res = INF; if i + s + 1 <= n { res = min(res, dp[i][i + s + 1][0] + s as i64 + 1); } if i + s + 1 <= n - 1 { res = min(res, dp[i][i + s + 1][1] + 1); } if i + s + 1 < n { res = max(res, a[i + s]); } dp[i][i + s][1] = res; //println!("dp[{}][{}] = {:?}", i, i + s, dp[i][i + s]); } } let mut mi = 1 << 58; for i in 0 .. n { mi = min(mi, min(dp[i][i][0], dp[i][i][1])); } mi } // Solved after reading the editorial fn main() { let n = get(); let a: Vec<i64> = (0.. n).map(|_| get()).collect(); println!("{}", solve(&a)); }