結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
|
提出日時 | 2022-11-27 22:55:07 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 1,350 bytes |
コンパイル時間 | 15,758 ms |
コンパイル使用メモリ | 403,788 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-04 14:35:59 |
合計ジャッジ時間 | 15,846 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
fn main() { let mut nk = String::new(); std::io::stdin().read_line(&mut nk).ok(); let nk: Vec<usize> = nk.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nk[0]; let k = nk[1]; let mut a = String::new(); std::io::stdin().read_line(&mut a).ok(); let a: Vec<isize> = a.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let k = (n-k).min(n-1); let mut summary = (0..n).map(|i| a[i] - a[0]).sum::<isize>(); let mut rights = (0..n).rev().take(k).collect::<Vec<_>>(); summary -= rights.iter().map(|&i| a[i] - a[0]).sum::<isize>() * 2; let mut lidx = 0usize; let mut result = summary; for i in 1..n { let diff = a[i] - a[i-1]; summary += i as isize * diff; summary -= lidx as isize * 2 * diff; summary -= (n - i) as isize * diff; summary += rights.len() as isize * 2 * diff; while lidx < n && !rights.is_empty() { let rval = rights[rights.len()-1]; if a[i] - a[lidx] <= a[rval] - a[i] { break; } else { summary -= (a[i] - a[lidx]) * 2; summary += (a[rval] - a[i]) * 2; lidx += 1; rights.pop(); } } result = result.min(summary); } println!("{}", result); }