結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
![]() |
提出日時 | 2021-02-12 21:54:50 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 5,924 bytes |
コンパイル時間 | 22,561 ms |
コンパイル使用メモリ | 378,264 KB |
実行使用メモリ | 29,528 KB |
最終ジャッジ日時 | 2024-07-19 21:11:36 |
合計ジャッジ時間 | 14,407 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
// ---------- begin Foldable Deque ----------pub struct FoldableDeque<T, F> {front: Vec<(T, T)>,back: Vec<(T, T)>,op: F,}#[allow(dead_code)]impl<T, F> FoldableDeque<T, F>whereT: Clone,F: Fn(&T, &T) -> T,{fn new(op: F) -> Self {FoldableDeque {front: Vec::new(),back: Vec::new(),op: op,}}fn find(&self) -> Option<T> {match (self.front.last(), self.back.last()) {(Some(a), Some(b)) => Some((self.op)(&a.1, &b.1)),(Some(a), None) => Some(a.1.clone()),(None, Some(b)) => Some(b.1.clone()),(None, None) => None,}}fn clear(&mut self) {self.front.clear();self.back.clear();}fn len(&self) -> usize {self.front.len() + self.back.len()}fn is_empty(&self) -> bool {self.len() == 0}fn push_back(&mut self, val: T) {let sum = self.back.last().map_or_else(|| val.clone(), |p| (self.op)(&p.1, &val));self.back.push((val, sum));}fn push_front(&mut self, val: T) {let sum = self.front.last().map_or_else(|| val.clone(), |p| (self.op)(&val, &p.1));self.front.push((val, sum));}fn pop_front(&mut self) -> Option<T> {if self.front.is_empty() {let a = self.back.clone();let m = (self.back.len() + 1) / 2;self.back.clear();let (f, b) = a.split_at(m);for v in f.iter().rev() {self.push_front(v.0.clone());}for v in b.iter() {self.push_back(v.0.clone());}}self.front.pop().map(|p| p.0)}fn pop_back(&mut self) -> Option<T> {if self.back.is_empty() {let a = self.front.clone();let m = (self.front.len() + 1) / 2;self.front.clear();let (f, b) = a.split_at(m);for v in b.iter() {self.push_front(v.0.clone());}for v in f.iter().rev() {self.push_back(v.0.clone());}}self.back.pop().map(|p| p.0)}fn front(&self) -> Option<&T> {self.front.last().map_or_else(|| self.back.get(0).map(|p| &p.0), |p| Some(&p.0))}fn back(&self) -> Option<&T> {self.back.last().map_or_else(|| self.front.get(0).map(|p| &p.0), |p| Some(&p.0))}}// ---------- end Foldable Deque ----------// ---------- begin input macro ----------// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}// ---------- end input macro ----------fn merge(a: &(i64, i64), b: &(i64, i64)) -> (i64, i64) {(a.0 + b.0, a.1 + b.1)}fn run() {input! {n: usize,k: usize,a: [i64; n],}let mut left_minus = FoldableDeque::new(merge);let mut left_plus = FoldableDeque::new(merge);let mut right_plus = FoldableDeque::new(merge);let mut right_minus = FoldableDeque::new(merge);for a in a.iter().take(k) {right_plus.push_back((*a, 1));}for a in a.iter().skip(k) {right_minus.push_back((*a, 1));}let find = |x: i64, p: (i64, i64)| -> i64 {x * p.1 - p.0};let x = a[0];let mut ans = 0;ans += left_minus.find().map_or(0, |p| -find(x, p));ans += left_plus.find().map_or(0, |p| find(x, p));ans += right_plus.find().map_or(0, |p| -find(x, p));ans += right_minus.find().map_or(0, |p| find(x, p));for i in 1..n {if right_plus.is_empty() {right_plus.push_back(right_minus.pop_front().unwrap());}left_plus.push_back(right_plus.pop_front().unwrap());let x = a[i];while left_plus.len() > 0 && right_minus.len() > 0 {let p = left_plus.front().unwrap().0;let q = right_minus.front().unwrap().0;if x - p >= q - x {left_minus.push_back(left_plus.pop_front().unwrap());right_plus.push_back(right_minus.pop_front().unwrap());} else {break;}}let mut val = 0;val += left_minus.find().map_or(0, |p| -find(x, p));val += left_plus.find().map_or(0, |p| find(x, p));val += right_plus.find().map_or(0, |p| -find(x, p));val += right_minus.find().map_or(0, |p| find(x, p));ans = ans.min(val);}println!("{}", ans);}fn main() {run();}