#907248 (Rust) No.1288 yuki collection

提出ソース
結果

問題	No.1288 yuki collection
ユーザー	37kt
提出日時	2023-08-24 15:15:09
言語	Rust (1.77.0)
結果	WA
実行時間	-
コード長	26,798 bytes
コンパイル時間	2,047 ms
コンパイル使用メモリ	167,836 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-08-24 15:15:38
合計ジャッジ時間	28,190 ms
ジャッジサーバーID （参考情報）	judge12 / judge13
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	WA	-
testcase_06	AC	1 ms 4,380 KB
testcase_07	AC	1 ms 4,384 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	2 ms 4,376 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	1 ms 4,380 KB
testcase_13	AC	679 ms 4,376 KB
testcase_14	WA	-
testcase_15	AC	475 ms 4,376 KB
testcase_16	AC	599 ms 4,376 KB
testcase_17	AC	685 ms 4,380 KB
testcase_18	WA	-
testcase_19	AC	593 ms 4,380 KB
testcase_20	AC	684 ms 4,380 KB
testcase_21	AC	403 ms 4,380 KB
testcase_22	AC	443 ms 4,376 KB
testcase_23	AC	496 ms 4,384 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	2,433 ms 4,380 KB
testcase_28	AC	1,415 ms 4,380 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	1,825 ms 4,376 KB
testcase_32	WA	-
testcase_33	AC	640 ms 4,376 KB
testcase_34	AC	603 ms 4,380 KB
testcase_35	AC	643 ms 4,376 KB
testcase_36	AC	158 ms 4,380 KB
testcase_37	AC	445 ms 4,380 KB
testcase_38	AC	638 ms 4,380 KB
testcase_39	AC	635 ms 4,376 KB
testcase_40	WA	-
testcase_41	AC	1 ms 4,376 KB
testcase_42	AC	1 ms 4,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
pub use __cargo_equip::prelude::*;

use min_cost_b_flow::MinCostBFlow;
#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};

fn main() {
    input! {
        n: usize,
        s: Bytes,
        a: [i64; n],
    }
    let mut g = MinCostBFlow::new();
    let mut vs = vec![vec![0; 5]; n + 1];
    let cv = |c: u8| match c {
        b'y' => 0,
        b'u' => 1,
        b'k' => 2,
        _ => 3,
    };
    for i in 0..=n {
        for j in 0..5 {
            vs[i][j] = g.add_vertex();
        }
    }
    for i in 0..n {
        for j in 0..5 {
            g.add_edge(vs[i][j], vs[i + 1][j], 0, 2000, 0);
        }
        let c = cv(s[i]);
        g.add_edge(vs[i][c], vs[i + 1][c + 1], 0, 1, -a[i]);
    }
    let (res, _) = g.min_cost_flow(vs[0][0], vs[n][4]).unwrap();
    println!("{}", -res);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`                                        licensed under `MIT/Apache-2.0`    as `crate::__cargo_equip::crates::__lazy_static_1_4_0`
///  - `min-cost-b-flow 0.1.0 (path+██████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::min_cost_b_flow`
///  - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)`                                           licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio`
/// 
///  # License and Copyright Notices
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      Copyright (c) 2010 The Rust Project Developers
/// 
///      Permission is hereby granted, free of charge, to any
///      person obtaining a copy of this software and associated
///      documentation files (the "Software"), to deal in the
///      Software without restriction, including without
///      limitation the rights to use, copy, modify, merge,
///      publish, distribute, sublicense, and/or sell copies of
///      the Software, and to permit persons to whom the Software
///      is furnished to do so, subject to the following
///      conditions:
/// 
///      The above copyright notice and this permission notice
///      shall be included in all copies or substantial portions
///      of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
///      ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
///      TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
///      PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
///      SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
///      CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
///      OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
///      IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
///      DEALINGS IN THE SOFTWARE.
///      ```
/// 
///  - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      The MIT License
///      Copyright 2019 (C) statiolake <statiolake@gmail.com>
/// 
///      Permission is hereby granted, free of charge, to any person obtaining a copy of
///      this software and associated documentation files (the "Software"), to deal in
///      the Software without restriction, including without limitation the rights to
///      use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
///      the Software, and to permit persons to whom the Software is furnished to do so,
///      subject to the following conditions:
/// 
///      The above copyright notice and this permission notice shall be included in all
///      copies or substantial portions of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
///      IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
///      FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
///      COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
///      IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
///      CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
/// 
///      Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019.  The
///      original macro is licensed under BSD 3-clause license.
/// 
///      Redistribution and use in source and binary forms, with or without
///      modification, are permitted provided that the following conditions are met:
/// 
///      1. Redistributions of source code must retain the above copyright notice, this
///         list of conditions and the following disclaimer.
/// 
///      2. Redistributions in binary form must reproduce the above copyright notice,
///         this list of conditions and the following disclaimer in the documentation
///         and/or other materials provided with the distribution.
/// 
///      3. Neither the name of the copyright holder nor the names of its contributors
///         may be used to endorse or promote products derived from this software
///         without specific prior written permission.
/// 
///      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
///      ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
///      WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
///      DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
///      FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
///      DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
///      SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
///      CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
///      OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
///      OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///      ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __lazy_static_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;extern crate core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy<T:Sync>(Cell<Option<T>>,Once);impl<T:Sync>Lazy<T>{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get<F>(&'static self,f:F)->&T where F:FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe impl<T:Sync>Sync for Lazy<T>{}#[macro_export]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;};}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub use core::ops::Deref as __Deref;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::__Deref for$N{type Target=$T;fn deref(&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!(LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::LazyStatic for$N{fn initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations)]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N=$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}}
        pub mod min_cost_b_flow {use std::{cmp::Reverse,collections::BinaryHeap};const UNREACHABLE:i64=std::i64::MAX;const SCALING_FACTOR:i64=2;#[derive(Debug,Clone,Copy)]pub struct Edge{pub from:usize,pub to:usize,pub lower:i64,pub upper:i64,pub cost:i64,pub gain:i64,pub flow:i64,}pub struct MinCostBFlow{n:usize,edges:Vec<Edge_>,head:Vec<usize>,next:Vec<usize>,b:Vec<i64>,farthest:i64,potential:Vec<i64>,dist:Vec<i64>,parent:Vec<usize>,pq:BinaryHeap<Reverse<(i64,usize)>>,excess_vs:Vec<usize>,deficit_vs:Vec<usize>,}impl MinCostBFlow{pub fn new()->Self{Self{n:0,edges:vec![],head:vec![],next:vec![],b:vec![],farthest:0,potential:vec![],dist:vec![],parent:vec![],pq:Default::default(),excess_vs:vec![],deficit_vs:vec![],}}pub fn add_vertex(&mut self)->usize{self.n+=1;self.head.push(!0);self.b.push(0);self.n-1}pub fn add_vertices(&mut self,size:usize)->Vec<usize>{self.n+=size;self.head.append(&mut vec![!0;size]);self.b.append(&mut vec![0;size]);(self.n-size..self.n).collect()}pub fn add_edge(&mut self,from:usize,to:usize,lower:i64,upper:i64,cost:i64)->usize{assert!(lower<=upper);assert!(from<self.n);assert!(to<self.n);let m=self.edges.len();self.next.push(self.head[from]);self.head[from]=m;self.next.push(self.head[to]);self.head[to]=m+1;self.edges.push(Edge_{to,cap:upper,cost,flow:0,});self.edges.push(Edge_{to:from,cap:-lower,cost:-cost,flow:0,});m/2}pub fn add_supply(&mut self,v:usize,amount:i64){self.b[v]+=amount;}pub fn add_demand(&mut self,v:usize,amount:i64){self.b[v]-=amount;}pub fn get_edge(&self,e:usize)->Edge{assert!(e<=self.edges.len()/2);let e=e*2;Edge{from:self.from(e),to:self.to(e),lower:self.lower(e),upper:self.upper(e),cost:self.cost(e),gain:self.gain(e),flow:self.flow(e),}}pub fn get_edges(&self)->Vec<Edge>{(0..self.edges.len()/2).map(|e|self.get_edge(e)).collect()}pub fn min_cost_b_flow(&mut self)->Result<i64,i64>{self.potential.resize(self.n,0);for u in 0..self.n{let mut e=self.head[u];while e!=!0{let rcap=self.residual_cap(e);if rcap<0{self.push(e,rcap);self.b[u]-=rcap;let v=self.to(e);self.b[v]+=rcap;}e=self.next[e];}}let mut inf_flow=1;for e in 0..self.edges.len(){inf_flow=inf_flow.max(self.residual_cap(e));}let mut delta=1;while delta*SCALING_FACTOR<=inf_flow{delta*=SCALING_FACTOR;}while delta>0{self.saturate_negative(delta);while self.dual(delta){self.primal(delta);}delta/=SCALING_FACTOR;}let mut value=0;for Edge_{flow,cost,..}in&self.edges{value+=flow*cost;}value/=2;if self.excess_vs.is_empty()&&self.deficit_vs.is_empty(){Ok(value)}else{Err(value)}}pub fn min_cost_flow(&mut self,s:usize,t:usize)->Result<(i64,i64),(i64,i64)>{assert!(s!=t);let mut inf_flow=self.b[s].abs();let mut e=self.head[s];while e!=!0{inf_flow+=0.max(self.edges[e].cap);e=self.next[e];}self.add_edge(t,s,0,inf_flow,0);if let Err(circulation_value)=self.min_cost_b_flow(){self.head[s]=self.next[s];self.head[t]=self.next[t];self.edges.pop();self.edges.pop();return Err((circulation_value,0));}let mut inf_flow=self.b[s].abs();let mut e=self.head[s];while e!=!0{inf_flow+=self.residual_cap(e);e=self.next[e];}self.b[s]+=inf_flow;self.b[t]-=inf_flow;let mf_value=match self.min_cost_b_flow(){Ok(v)=>v,Err(v)=>v,};self.b[s]-=inf_flow;self.b[t]+=inf_flow;self.head[s]=self.next[s];self.head[t]=self.next[t];self.edges.pop();self.edges.pop();Ok((mf_value,self.b[t]))}pub fn get_result_value_i128(&mut self)->i128{let mut value=0;for e in&self.edges{value+=e.flow as i128*e.cost as i128;}value/2}pub fn get_potential(&mut self)->Vec<i64>{self.potential=vec![0;self.n];for _ in 0..self.n{for e in 0..self.edges.len(){if self.residual_cap(e)>0{let to=self.to(e);self.potential[to]=self.potential[to].min(self.potential[self.from(e)]+self.cost(e));}}}self.potential.clone()}fn from(&self,e:usize)->usize{self.edges[e^1].to}fn to(&self,e:usize)->usize{self.edges[e].to}fn flow(&self,e:usize)->i64{self.edges[e].flow}fn lower(&self,e:usize)->i64{-self.edges[e^1].cap}fn upper(&self,e:usize)->i64{self.edges[e].cap}fn cost(&self,e:usize)->i64{self.edges[e].cost}fn gain(&self,e:usize)->i64{-self.edges[e].cost}fn push(&mut self,e:usize,amount:i64){self.edges[e].flow+=amount;self.edges[e^1].flow-=amount;}fn residual_cost(&self,e:usize)->i64{self.cost(e)+self.potential[self.from(e)]-self.potential[self.to(e)]}fn residual_cap(&self,e:usize)->i64{self.edges[e].cap-self.edges[e].flow}fn dual(&mut self,delta:i64)->bool{self.dist=vec![UNREACHABLE;self.n];self.parent=vec![!0;self.n];for i in(0..self.excess_vs.len()).rev(){if self.b[self.excess_vs[i]]<delta{self.excess_vs.swap_remove(i);}}for i in(0..self.deficit_vs.len()).rev(){if self.b[self.deficit_vs[i]]>-delta{self.deficit_vs.swap_remove(i);}}for&v in&self.excess_vs{self.dist[v]=0;self.pq.push(Reverse((0,v)));}self.farthest=0;let mut deficit_count=0;while let Some(Reverse((d,u)))=self.pq.pop(){if self.dist[u]<d{continue;}self.farthest=d;if self.b[u]<=-delta{deficit_count+=1;}if deficit_count>=self.deficit_vs.len(){break;}let mut e=self.head[u];while e!=!0{if self.residual_cap(e)>=delta{let v=self.to(e);let new_dist=d+self.residual_cost(e);if self.dist[v]>new_dist{self.dist[v]=new_dist;self.pq.push(Reverse((new_dist,v)));self.parent[v]=e;}}e=self.next[e];}}self.pq.clear();for v in 0..self.n{self.potential[v]+=self.dist[v].min(self.farthest);}deficit_count>0}fn primal(&mut self,delta:i64){for i in 0..self.deficit_vs.len(){let t=self.deficit_vs[i];if self.dist[t]>self.farthest{continue;}let mut f=-self.b[t];let mut v=t;while self.parent[v]!=!0&&f>=delta{f=f.min(self.residual_cap(self.parent[v]));v=self.from(self.parent[v]);}f=f.min(self.b[v]);if f<delta{continue;}v=t;while self.parent[v]!=!0{self.push(self.parent[v],f);let u=self.from(self.parent[v]);self.parent[v]=!0;v=u;}self.b[t]+=f;self.b[v]-=f;}}fn saturate_negative(&mut self,delta:i64){self.excess_vs.clear();self.deficit_vs.clear();for u in 0..self.n{let mut e=self.head[u];while e!=!0{let rcap=self.residual_cap(e);let rcost=self.residual_cost(e);if rcost<0&&rcap>=delta{self.push(e,rcap);self.b[u]-=rcap;let v=self.to(e);self.b[v]+=rcap;}e=self.next[e];}}for v in 0..self.n{if self.b[v]>0{self.excess_vs.push(v);}else if self.b[v]<0{self.deficit_vs.push(v);}}}}struct Edge_{to:usize,cap:i64,cost:i64,flow:i64,}}
        pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}impl Readable for Chars{type Output=Vec<char>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<char>{source.next_token_unwrap().chars().collect()}}pub enum Bytes{}impl Readable for Bytes{type Output=Vec<u8>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<u8>{source.next_token_unwrap().bytes().collect()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}pub enum Isize1{}impl Readable for Isize1{type Output=isize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,current_context:Box<str>,reader:R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R>{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->LineSource<BufReader<&'a[u8]>>{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,context:Box<str>,_read:PhantomData<R>,}impl<R:BufRead>OnceSource<R>{pub fn new(mut source:R)->OnceSource<R>{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}impl<R:BufRead>Source<R>for OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->OnceSource<BufReader<&'a[u8]>>{OnceSource::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source<R:BufRead>{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl<R:BufRead,S:Source<R>>Source<R>for&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Self::Output;}impl<T:FromStr>Readable for T where T::Err:Debug,{type Output=T;fn read<R:BufRead,S:Source<R>>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::<T>(),err=e,),}}}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex<AutoSource<BufReader<Stdin>>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin())));}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{(@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=<usize as$crate::__cargo_equip::crates::proconio::__Readable>::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::<Vec<_>>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input.  ","This is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::__Readable>::read($source)}}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));lock.is_empty()}}
    }

    pub(crate) mod macros {
        pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};}
        pub mod min_cost_b_flow {}
        pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value};}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};}

    mod preludes {
        pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;}
        pub mod min_cost_b_flow {}
        pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__lazy_static_1_4_0 as lazy_static;}
    }
}
yukicoder

結果

テストケース

ソースコード
