// 問題文と制約は読みましたか? // #[fastout] fn main() { input! { n: usize, m: usize, xs: [i64; n], // 焼き肉の料金 ys: [i64; n], // 交通費 } let ds = izip!(&xs, &ys).map(|(&x, &y)| (x - y).max(0)).collect_vec(); let ds_cumsum = CumSum::new(&ds); let ans = (0..n - m + 1) .map(|begin| { let end = begin + m; ds_cumsum.range_sum(begin..end) }) .max() .unwrap(); println!("{}", ans); } // ====== import ====== #[allow(unused_imports)] use { itertools::{Itertools, chain, iproduct, izip}, proconio::{ derive_readable, fastout, input, marker::{Bytes, Chars, Usize1}, }, std::{ cmp::Reverse, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet}, }, }; // ====== output func ====== #[allow(unused_imports)] use print_util::*; pub mod print_util { use itertools::Itertools; use proconio::fastout; #[fastout] pub fn print_vec(arr: &[T]) { for a in arr { println!("{}", a); } } #[fastout] pub fn print_vec_1line(arr: &[T]) { println!("{}", arr.iter().join(" ")); } #[fastout] pub fn print_vec2>(arr: &[R]) { for row in arr { println!("{}", row.as_ref().iter().join(" ")); } } pub fn print_bytes(bytes: &[u8]) { println!("{}", std::str::from_utf8(bytes).unwrap()); } pub fn print_chars(chars: &[char]) { println!("{}", chars.iter().collect::()); } #[fastout] pub fn print_vec_bytes>(vec_bytes: &[R]) { for row in vec_bytes { println!("{}", std::str::from_utf8(row.as_ref()).unwrap()); } } #[fastout] pub fn print_vec_chars>(vec_chars: &[R]) { for row in vec_chars { println!("{}", row.as_ref().iter().collect::()); } } pub fn print_yesno(ans: bool) { println!("{}", if ans { "Yes" } else { "No" }); } } // ====== snippet ====== use cumsum::*; #[allow(clippy::module_inception)] pub mod cumsum { pub fn prefix_sum(xs: &[i64]) -> Vec { let mut prefix_sum = vec![0; xs.len() + 1]; for i in 1..xs.len() + 1 { prefix_sum[i] = prefix_sum[i - 1] + xs[i - 1]; } prefix_sum } use std::ops::{Bound, Range, RangeBounds}; #[derive(Clone, Debug, PartialEq, Eq)] pub struct CumSum { pub cumsum: Vec, } impl CumSum { /// # 計算量 /// O(|xs|) pub fn new(xs: &[i64]) -> CumSum { let mut cumsum = vec![0; xs.len() + 1]; for i in 1..xs.len() + 1 { cumsum[i] = cumsum[i - 1] + xs[i - 1]; } CumSum { cumsum } } fn open(&self, range: impl RangeBounds) -> Range { use Bound::Excluded; use Bound::Included; use Bound::Unbounded; let begin = match range.start_bound() { Unbounded => 0, Included(&x) => x, Excluded(&x) => x + 1, }; let end = match range.end_bound() { Excluded(&x) => x, Included(&x) => x + 1, Unbounded => self.cumsum.len() - 1, }; begin..end } /// 区間 `[begin, end)` の要素の和を計算します。 /// # 計算量 /// O(1) pub fn range_sum(&self, range: impl RangeBounds) -> i64 { let range = self.open(range); self.cumsum[range.end] - self.cumsum[range.start] } /// 区間 `[0, end)` での和を計算します。 /// # 計算量 /// O(1) pub fn prefix_sum(&self, end: usize) -> i64 { self.cumsum[end] } /// 区間 `[begin, n)` の要素の和を計算します。(`n` は元の配列の長さ) /// # 計算量 /// O(1) pub fn suffix_sum(&self, begin: usize) -> i64 { self.cumsum[self.cumsum.len() - 1] - self.cumsum[begin] } /// `f(sum(l..r))` が `true` となる最大の `r in [l, n]` を見つける。 /// `n` は元の配列の長さ。 /// `f` は単調でなければならない。 /// `f(sum(l..i))` が `true` => `f(sum(l..j))` が `true` for all `l <= j <= i`. /// # Panics /// `l > n` の場合にパニックする。 /// # 計算量 /// O(log n) pub fn max_right(&self, l: usize, mut f: F) -> usize where F: FnMut(i64) -> bool, { let n = self.cumsum.len() - 1; assert!(l <= n); assert!(f(0), "f(0) must be true"); if f(self.range_sum(l..n)) { return n; } let mut ok = l; let mut ng = n + 1; while ng - ok > 1 { let mid = ok + (ng - ok) / 2; if f(self.range_sum(l..mid)) { ok = mid; } else { ng = mid; } } ok } /// `f(sum(l..r))` が `true` となる最小の `l in [0, r]` を見つける。 /// `f` は単調でなければならない。 /// `f(sum(i..r))` が `true` => `f(sum(j..r))` が `true` for all `i <= j <= r`. /// `r > n` の場合にパニックする。 /// # 計算量 /// O(log r) pub fn min_left(&self, r: usize, mut f: F) -> usize where F: FnMut(i64) -> bool, { let n = self.cumsum.len() - 1; assert!(r <= n); assert!(f(0), "f(0) must be true"); if f(self.range_sum(0..r)) { return 0; } let mut ok = r; let mut ng = 0; while ok - ng > 1 { let mid = ng + (ok - ng) / 2; if f(self.range_sum(mid..r)) { ok = mid; } else { ng = mid; } } ok } } }