結果
問題 | No.2601 Very Poor |
ユーザー | naut |
提出日時 | 2024-01-12 21:45:04 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 406 ms / 2,000 ms |
コード長 | 5,192 bytes |
コンパイル時間 | 1,493 ms |
コンパイル使用メモリ | 189,204 KB |
実行使用メモリ | 14,236 KB |
最終ジャッジ日時 | 2024-03-20 19:46:27 |
合計ジャッジ時間 | 10,212 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 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 | 2 ms
6,548 KB |
testcase_06 | AC | 2 ms
6,548 KB |
testcase_07 | AC | 4 ms
6,548 KB |
testcase_08 | AC | 3 ms
6,548 KB |
testcase_09 | AC | 3 ms
6,548 KB |
testcase_10 | AC | 2 ms
6,548 KB |
testcase_11 | AC | 3 ms
6,548 KB |
testcase_12 | AC | 3 ms
6,548 KB |
testcase_13 | AC | 3 ms
6,548 KB |
testcase_14 | AC | 2 ms
6,548 KB |
testcase_15 | AC | 370 ms
14,236 KB |
testcase_16 | AC | 352 ms
14,236 KB |
testcase_17 | AC | 390 ms
14,236 KB |
testcase_18 | AC | 404 ms
14,236 KB |
testcase_19 | AC | 400 ms
14,236 KB |
testcase_20 | AC | 381 ms
14,236 KB |
testcase_21 | AC | 391 ms
14,236 KB |
testcase_22 | AC | 401 ms
14,236 KB |
testcase_23 | AC | 380 ms
14,236 KB |
testcase_24 | AC | 401 ms
14,236 KB |
testcase_25 | AC | 406 ms
14,236 KB |
testcase_26 | AC | 404 ms
14,236 KB |
testcase_27 | AC | 398 ms
14,236 KB |
testcase_28 | AC | 393 ms
14,236 KB |
testcase_29 | AC | 397 ms
14,236 KB |
testcase_30 | AC | 391 ms
14,236 KB |
testcase_31 | AC | 396 ms
14,236 KB |
testcase_32 | AC | 403 ms
14,236 KB |
testcase_33 | AC | 396 ms
14,236 KB |
testcase_34 | AC | 396 ms
14,236 KB |
testcase_35 | AC | 2 ms
6,548 KB |
testcase_36 | AC | 3 ms
6,548 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 X = input!(usize); let mut A = input!(usize, N); let B = { let mut a = vec![]; a.append(&mut A.clone()); a.append(&mut A); a }; let stree = SegmentTree::from(&B, |x, y| x + y, 0); let mut ans = 0; for i in 0..N { let mut ok = 0; let mut ng = N + 1; while ng - ok > 1 { let m = (ok + ng) / 2; if stree.prod(i..i + m) > X { ng = m; } else { ok = m; } } ans = std::cmp::max(ans, stree.prod(i..i + ok)); } writeln!(out, "{}", ans); } 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()) } } } } pub struct SegmentTree<M> { size: usize, tree: Vec<M>, op: fn(&M, &M) -> M, id: M, } impl<M: Copy + PartialEq> SegmentTree<M> { /// self.tree = [id; size], self.op = op, self.id = id pub fn new(size: usize, op: fn(&M, &M) -> M, id: M) -> Self { return Self { size: size, tree: vec![id; 2 * size], op: op, id: id, }; } /// self.tree = arr, self.op = op, self.id = id pub fn from(arr: &[M], op: fn(&M, &M) -> M, id: M) -> Self { let size = arr.len(); let mut tree = vec![id; 2 * size]; for i in 0..size { tree[i + size] = arr[i]; assert!( op(&id, &arr[i]) == arr[i], "id is not the identity element of given operator" ); } for i in (1..size).rev() { tree[i] = op(&tree[i << 1], &tree[i << 1 | 1]); } return Self { size: size, tree: tree, op: op, id: id, }; } /// self.tree[pos] <- value pub fn insert(&mut self, mut pos: usize, value: M) -> () { pos += self.size; self.tree[pos] = value; while pos > 1 { pos >>= 1; self.tree[pos] = (self.op)(&self.tree[pos << 1], &self.tree[pos << 1 | 1]); } } /// return self.tree[pos] (syntax sugar: self[pos]) pub fn get_point(&self, pos: usize) -> M { return self[pos]; } /// return Π_{i ∈ [left, right)} self.tree[i] pub fn get(&self, left: usize, right: usize) -> M { let (mut l, mut r) = (left + self.size, right + self.size); let (mut vl, mut vr) = (self.id, self.id); while l < r { if l & 1 == 1 { vl = (self.op)(&vl, &self.tree[l]); l += 1; } if r & 1 == 1 { r -= 1; vr = (self.op)(&self.tree[r], &vr); } l >>= 1; r >>= 1; } return (self.op)(&vl, &vr); } /// return Π_{i ∈ range} self.tree[i] pub fn prod<R: std::ops::RangeBounds<usize>>(&self, range: R) -> M { 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 + 1, std::ops::Bound::Excluded(&r) => r, std::ops::Bound::Unbounded => self.size, }; return self.get(left, right); } } impl<M> std::ops::Index<usize> for SegmentTree<M> { type Output = M; fn index(&self, index: usize) -> &Self::Output { &self.tree[index + self.size] } } impl<M: std::fmt::Display> std::fmt::Display for SegmentTree<M> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!( f, "{}", self.tree[self.size..] .iter() .map(|x| x.to_string()) .collect::<Vec<_>>() .join(" ") ) } }