結果
問題 | No.2694 The Early Bird Catches The Worm |
ユーザー | naut |
提出日時 | 2024-03-22 22:05:02 |
言語 | Rust (1.77.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,911 bytes |
コンパイル時間 | 2,076 ms |
コンパイル使用メモリ | 187,728 KB |
実行使用メモリ | 10,112 KB |
最終ジャッジ日時 | 2024-03-22 22:05:09 |
合計ジャッジ時間 | 5,393 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,548 KB |
testcase_01 | AC | 1 ms
6,548 KB |
testcase_02 | AC | 1 ms
6,548 KB |
testcase_03 | AC | 1 ms
6,548 KB |
testcase_04 | AC | 1 ms
6,548 KB |
testcase_05 | AC | 1 ms
6,548 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 1 ms
6,548 KB |
testcase_10 | AC | 1 ms
6,548 KB |
testcase_11 | AC | 1 ms
6,548 KB |
testcase_12 | AC | 1 ms
6,548 KB |
testcase_13 | AC | 1 ms
6,548 KB |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 1 ms
6,548 KB |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | AC | 36 ms
8,704 KB |
testcase_50 | AC | 36 ms
8,704 KB |
testcase_51 | AC | 36 ms
8,704 KB |
testcase_52 | AC | 36 ms
8,704 KB |
testcase_53 | AC | 36 ms
8,704 KB |
testcase_54 | WA | - |
testcase_55 | WA | - |
testcase_56 | WA | - |
testcase_57 | WA | - |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | WA | - |
testcase_61 | WA | - |
testcase_62 | WA | - |
testcase_63 | WA | - |
testcase_64 | WA | - |
testcase_65 | WA | - |
testcase_66 | WA | - |
testcase_67 | WA | - |
testcase_68 | WA | - |
testcase_69 | AC | 36 ms
10,112 KB |
testcase_70 | AC | 36 ms
10,112 KB |
testcase_71 | AC | 36 ms
10,112 KB |
testcase_72 | AC | 36 ms
10,112 KB |
testcase_73 | AC | 36 ms
10,112 KB |
testcase_74 | AC | 17 ms
6,548 KB |
testcase_75 | AC | 35 ms
10,112 KB |
ソースコード
#![allow(non_snake_case, unused_imports, unused_must_use)] use std::io::{self, prelude::*}; use std::str; fn main() { let (stdin, stdout) = (io::stdin(), io::stdout()); let mut scan = Scanner::new(stdin.lock()); let mut out = io::BufWriter::new(stdout.lock()); macro_rules! input { ($T: ty) => { scan.token::<$T>() }; ($T: ty, $N: expr) => { (0..$N).map(|_| scan.token::<$T>()).collect::<Vec<_>>() }; } let N = input!(usize); let H = input!(isize); let A = input!(isize, N); let B = input!(isize, N); let mut BIT_A = BinaryIndexedTree::new(N); let mut BIT_B = BinaryIndexedTree::new(N); for i in 0..N { BIT_A.add(i, A[i]); BIT_B.add(i, B[i]); } let mut ans = 0; let mut right = 0; let mut h_now = 0; for left in 0..N { loop { if right < N { h_now += B[right] * (right + 1 - left) as isize; right += 1; } else { break; } if h_now > H { right -= 1; h_now -= B[right] * (right + 1 - left) as isize; break; } } if left + 1 < right { ans = std::cmp::max(ans, BIT_A.sum(left..right)); h_now -= BIT_B.sum(left..right); } } writeln!(out, "{}", ans); } pub struct BinaryIndexedTree<T> { tree: Vec<T>, } impl<T: Default + Clone + Copy + std::ops::AddAssign + std::ops::Sub<Output = T>> BinaryIndexedTree<T> { /// self = [0; size] pub fn new(size: usize) -> Self { return Self { tree: vec![T::default(); size + 1], }; } /// self[i] <- self[i] + w pub fn add(&mut self, i: usize, w: T) { self._inner_add(i + 1, w); } /// return Σ_{j ∈ [0, i]} self[j] pub fn prefix_sum(&self, i: usize) -> T { self._inner_sum(i + 1) } /// return Σ_{j ∈ range} self[j] pub fn sum<R: std::ops::RangeBounds<usize>>(&self, range: R) -> T { let left = match range.start_bound() { std::ops::Bound::Included(&l) => l, std::ops::Bound::Excluded(&l) => l + 1, std::ops::Bound::Unbounded => 0, }; let right = match range.end_bound() { std::ops::Bound::Included(&r) => r, std::ops::Bound::Excluded(&r) => r - 1, std::ops::Bound::Unbounded => self.tree.len() - 2, }; if left == 0 { return self.prefix_sum(right); } else { return self.prefix_sum(right) - self.prefix_sum(left - 1); } } fn _inner_add(&mut self, mut i: usize, w: T) { while i < self.tree.len() { self.tree[i] += w; i += i & i.wrapping_neg(); } } fn _inner_sum(&self, mut i: usize) -> T { let mut ret = T::default(); while i > 0 { ret += self.tree[i]; i -= i & i.wrapping_neg(); } return ret; } } struct Scanner<R> { reader: R, buf_str: Vec<u8>, buf_iter: str::SplitWhitespace<'static>, } impl<R: BufRead> Scanner<R> { fn new(reader: R) -> Self { Self { reader, buf_str: vec![], buf_iter: "".split_whitespace(), } } fn token<T: str::FromStr>(&mut self) -> T { loop { if let Some(token) = self.buf_iter.next() { return token.parse().ok().expect("Failed parse"); } self.buf_str.clear(); self.reader .read_until(b'\n', &mut self.buf_str) .expect("Failed read"); self.buf_iter = unsafe { let slice = str::from_utf8_unchecked(&self.buf_str); std::mem::transmute(slice.split_whitespace()) } } } }