結果
問題 | No.2601 Very Poor |
ユーザー |
![]() |
提出日時 | 2024-01-12 21:45:04 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 5,192 bytes |
コンパイル時間 | 11,097 ms |
コンパイル使用メモリ | 379,040 KB |
実行使用メモリ | 14,372 KB |
最終ジャッジ日時 | 2024-09-30 06:20:08 |
合計ジャッジ時間 | 19,241 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#![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 = idpub 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 = idpub 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] <- valuepub 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(" "))}}