#1053253 (Rust) No.2713 Just Solitaire

• 問題: No.2713 Just Solitaire
• ユーザー: 37kt
• 提出日時: 2025-03-16 13:16:29
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 15,551 bytes
• コンパイル時間: 15,939 ms
• コンパイル使用メモリ: 397,672 KB
• 実行使用メモリ: 7,324 KB
• 最終ジャッジ日時: 2025-03-16 13:16:59
• 合計ジャッジ時間: 17,536 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	AC * 2
other	AC * 32

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// verification-helper: PROBLEM https://yukicoder.me/problems/no/2713
pub use __cargo_equip::prelude::*;
use binary_optimization::BinaryOptimization;
use proconio::{fastout, input, marker::Usize1};
#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
        a: [i64; n],
        b: [i64; m],
        c: [[Usize1]; m],
    }
    let mut opt = BinaryOptimization::new(n);
    for i in 0..n {
        opt.add_1(i, |bi| [0, a[i]][bi]);
    }
    for i in 0..m {
        opt.add_all1(&c[i], -b[i]);
    }
    let (cost, _) = opt.solve();
    println!("{}", -cost);
}
// The following code was expanded by `cargo-equip`.
///  # Bundled libraries
/// 
///  - `binary_optimization 0.1.0 (path+████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as 
    `crate::__cargo_equip::crates::binary_optimization`
///  - `max_flow 0.1.0 (path+█████████████████████████████████████████)`                       published in **missing** licensed under `CC0-1.0` as 
    `crate::__cargo_equip::crates::__max_flow_0_1_0`
///  - `numeric_traits 0.1.0 (path+██████████████████████████████████████████████████)`        published in **missing** licensed under `CC0-1.0` as 
    `crate::__cargo_equip::crates::__numeric_traits_0_1_0`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod binary_optimization {use crate::__cargo_equip::preludes::binary_optimization::*;use std::borrow::Borrow;use max_flow::MaxFlow;#[derive
            (Clone)]pub struct BinaryOptimization{n_item:usize,n_aux:usize,src:usize,dst:usize,cost_0:i64,cost_1:Vec<[i64;2]>,edges:Vec<(usize,usize
            ,i64)>,}impl BinaryOptimization{pub fn new(n:usize)->Self{Self{n_item:n,n_aux:0,src:n,dst:n+1,cost_0:0,cost_1:vec![[0;2];n],edges:vec![]
            ,}}pub fn add(&mut self,cost:i64){self.cost_0+=cost;}pub fn add_1(&mut self,i:usize,mut cost:impl FnMut(usize)->i64){self.cost_1[i][0]
            +=cost(0);self.cost_1[i][1]+=cost(1);}pub fn add_2(&mut self,i:usize,j:usize,mut cost:impl FnMut(usize,usize)->i64){let mut x:[[i64;2];2]
            =[[0;2];2];for bi in 0..2{for bj in 0..2{x[bi][bj]=cost(bi,bj);}}assert!(x[0][0]+x[1][1]<=x[0][1]+x[1][0],"must be monge");self.add
            (x[0][0]);self.add_1(i,|bi|[0,x[1][0]-x[0][0]][bi]);self.add_1(j,|bj|[0,x[1][1]-x[1][0]][bj]);self.add_edge(i,j,(x[0][1]+x[1][0])-(x[0][0]
            +x[1][1]));}pub fn add_3(&mut self,i:usize,j:usize,k:usize,mut cost:impl FnMut(usize,usize,usize)->i64,){assert!(i!=j&&j!=k&&k!=i);let a
            =cost(0,0,0);let b=cost(0,0,1);let c=cost(0,1,0);let d=cost(0,1,1);let e=cost(1,0,0);let f=cost(1,0,1);let g=cost(1,1,0);let h=cost(1,1,1
            );let p=(a+d+f+g)-(b+c+e+h);if p>=0{let p1=f-b;let p2=g-e;let p3=d-c;let p12=(c+e)-(a+g);let p23=(b+c)-(a+d);let p31=(b+e)-(a+f);self.add
            (a);self.add_1(i,|bi|[0,p1][bi]);self.add_1(j,|bj|[0,p2][bj]);self.add_1(k,|bk|[0,p3][bk]);self.add_2(i,j,|bi,bj|[[0,p12],[0,0]][bi][bj]
            );self.add_2(j,k,|bj,bk|[[0,p23],[0,0]][bj][bk]);self.add_2(k,i,|bk,bi|[[0,p31],[0,0]][bk][bi]);self.add_all1([i,j,k],p);}else{}}pub fn 
            add_all0<I>(&mut self,items:I,cost:i64)where I:IntoIterator,I::Item:Borrow<usize>,{let mut items=items.into_iter().map(|x|*x.borrow
            ()).collect::<Vec<_>>();items.sort_unstable();items.dedup();match&items[..]{[]=>self.add(cost),&[i]=>self.add_1(i,|bi|[cost,0][bi]),&[i,j]
            =>self.add_2(i,j,|bi,bj|[[cost,0],[0,0]][bi][bj]),items=>{self.add(cost);let aux=self.n_item+2+self.n_aux;self.n_aux+=1;self.add_edge(self
            .src,aux,-cost);for&i in items{self.add_edge(aux,i,-cost);}}}}pub fn add_all1<I>(&mut self,items:I,cost:i64)where I:IntoIterator,I::Item
            :Borrow<usize>,{let mut items=items.into_iter().map(|x|*x.borrow()).collect::<Vec<_>>();items.sort_unstable();items.dedup();match&items[
            ..]{[]=>self.add(cost),&[i]=>self.add_1(i,|bi|[0,cost][bi]),&[i,j]=>self.add_2(i,j,|bi,bj|[[0,0],[0,cost]][bi][bj]),items=>{self.add(cost
            );let aux=self.n_item+2+self.n_aux;self.n_aux+=1;for&i in items{self.add_edge(i,aux,-cost);}self.add_edge(aux,self.dst,-cost);}}}pub fn 
            add_any0<I>(&mut self,items:I,cost:i64)where I:IntoIterator,I::Item:Borrow<usize>,{self.add(cost);self.add_all1(items,-cost);}pub fn 
            add_any1<I>(&mut self,items:I,cost:i64)where I:IntoIterator,I::Item:Borrow<usize>,{self.add(cost);self.add_all0(items,-cost);}pub fn solve
            (&mut self)->(i64,Vec<usize>){for i in 0..self.n_item{let cost=self.cost_1[i];if cost[0]<cost[1]{self.add(cost[0]);self.add_edge(self.src
            ,i,cost[1]-cost[0]);}else{self.add(cost[1]);self.add_edge(i,self.dst,cost[0]-cost[1]);}self.cost_1[i]=[0;2];}let mut flow=MaxFlow::new
            ();flow.add_vertices(self.n_item+2+self.n_aux);for&(i,j,cost)in&self.edges{flow.add_edge(i,j,cost);}let cost=self.cost_0+flow.max_flow
            (self.src,self.dst);let mut cut=flow.min_cut(self.dst);cut.truncate(self.n_item);let choice=cut.into_iter().map(|i|i as usize).collect
            ();(cost,choice)}fn add_edge(&mut self,i:usize,j:usize,cost:i64){assert!(cost>=0);assert!(i!=j);if cost==0{return;}self.edges.push((i,j
            ,cost));}}}
        pub mod __max_flow_0_1_0 {use crate::__cargo_equip::preludes::__max_flow_0_1_0::*;use std::iter::FusedIterator;use numeric_traits::{Inf
            ,Integer};mod internal{use crate::__cargo_equip::preludes::__max_flow_0_1_0::*;#[derive(Clone,Copy)]pub(in crate::__cargo_equip::crates
            ::__max_flow_0_1_0)struct Edge{pub(in crate::__cargo_equip::crates::__max_flow_0_1_0)dst:usize,pub(in crate::__cargo_equip::crates
            ::__max_flow_0_1_0)cap:i64,}#[derive(Clone)]pub(in crate::__cargo_equip::crates::__max_flow_0_1_0)struct Queue{data:Vec<usize>,head:usize
            ,tail:usize,}impl Queue{pub(in crate::__cargo_equip::crates::__max_flow_0_1_0)fn new()->Self{Self{data:vec![],head:0,tail:0,}}pub(in crate
            ::__cargo_equip::crates::__max_flow_0_1_0)fn set_capacity(&mut self,cap:usize){self.data.resize(cap,0);}pub(in crate::__cargo_equip
            ::crates::__max_flow_0_1_0)fn clear(&mut self){self.head=0;self.tail=0;}pub(in crate::__cargo_equip::crates::__max_flow_0_1_0)fn push(&mut 
            self,v:usize){self.data[self.tail]=v;self.tail+=1;}pub(in crate::__cargo_equip::crates::__max_flow_0_1_0)fn pop(&mut self)->Option<usize>{
            (self.head!=self.tail).then(||{self.head+=1;self.data[self.head-1]})}}}#[derive(Clone)]pub struct MaxFlow{edges:Vec<internal::Edge>,head
            :Vec<usize>,next:Vec<usize>,dist:Vec<i32>,iter:Vec<usize>,queue:internal::Queue,}#[derive(Debug,Clone,Copy)]pub struct Edge{pub src:usize
            ,pub dst:usize,pub cap:i64,pub flow:i64,}impl MaxFlow{pub fn new()->Self{Self{edges:vec![],head:vec![],next:vec![],dist:vec![],iter:vec![]
            ,queue:internal::Queue::new(),}}pub fn count_vertices(&self)->usize{self.head.len()}pub fn add_vertex(&mut self)->usize{self.head.push(!0
            );self.head.len()-1}pub fn add_vertices(&mut self,n:usize)->Vec<usize>{self.head.resize(self.head.len()+n,!0);(self.head.len()-n..self
            .head.len()).collect()}pub fn add_edge(&mut self,src:usize,dst:usize,cap:i64)->usize{assert!(src<self.count_vertices());assert!(dst<self
            .count_vertices());assert!(cap>=0);let m=self.edges.len();self.next.push(self.head[src]);self.head[src]=m;self.next.push(self.head[dst]
            );self.head[dst]=m+1;self.edges.push(internal::Edge{dst,cap});self.edges.push(internal::Edge{dst:src,cap:0});m/2}pub fn edges(&self
            ,)->impl Iterator<Item=Edge>+DoubleEndedIterator+ExactSizeIterator+FusedIterator+'_{self.edges.windows(2).map(|e|Edge{src:e[1].dst,dst
            :e[0].dst,cap:e[0].cap+e[1].cap,flow:e[1].cap,})}pub fn max_flow(&mut self,src:usize,dst:usize)->i64{assert!(src!=dst);assert!(src<self
            .count_vertices());assert!(dst<self.count_vertices());let max_cap=self.edges.iter().map(|e|e.cap).max().unwrap_or(0);if max_cap==0{return 
            0;}self.iter.resize(self.count_vertices(),0);self.dist.resize(self.count_vertices(),0);let mut flow=0;for f in(0..=max_cap.floor_log2
            ()).map(|i|1<<i).rev(){while self.build_augmenting_path(src,dst,f){self.iter.copy_from_slice(&self.head);flow+=self.find_augmenting_path
            (src,dst,f,i64::inf());}}flow}pub fn min_cut(&mut self,src:usize)->Vec<bool>{let mut vis=vec![false;self.count_vertices()];self.queue
            .clear();self.queue.set_capacity(self.count_vertices());vis[src]=true;self.queue.push(src);while let Some(v)=self.queue.pop(){let mut ei
            =self.head[v];while ei!=!0{let e=self.edges[ei];if e.cap>0&&!vis[e.dst]{vis[e.dst]=true;self.queue.push(e.dst);}ei=self.next[ei];}}vis}fn 
            build_augmenting_path(&mut self,src:usize,dst:usize,base:i64)->bool{self.dist.fill(i32::inf());self.queue.clear();self.queue.set_capacity
            (self.count_vertices());self.dist[src]=0;self.queue.push(src);while let Some(v)=self.queue.pop(){let mut ei=self.head[v];while ei!=!0{let 
            e=self.edges[ei];if e.cap>=base&&self.dist[e.dst]==i32::inf(){self.dist[e.dst]=self.dist[v]+1;self.queue.push(e.dst);if e.dst==dst{return 
            true;}}ei=self.next[ei];}}false}fn find_augmenting_path(&mut self,v:usize,dst:usize,base:i64,flow:i64)->i64{if v==dst{return flow;}let mut 
            sum=0;while self.iter[v]!=!0{let e=self.edges[self.iter[v]];if e.cap>=base&&self.dist[v]<self.dist[e.dst]{let diff=self
            .find_augmenting_path(e.dst,dst,base,e.cap.min(flow-sum));if diff>0{self.edges[self.iter[v]].cap-=diff;self.edges[self.iter[v]^1].cap
            +=diff;sum+=diff;if flow-sum<base{break;}}}self.iter[v]=self.next[self.iter[v]];}sum}}}
        pub mod __numeric_traits_0_1_0 {pub mod inf{pub trait Inf:PartialOrd{fn inf()->Self;}pub trait NegInf:PartialOrd{fn neg_inf()->Self
            ;}macro_rules!impl_inf{($($t:ty,$inf:expr,)*)=>{$(impl Inf for$t{fn inf()->Self{$inf}})*}}macro_rules!impl_neg_inf{($($t:ty,$neg_inf:expr
            ,)*)=>{$(impl NegInf for$t{fn neg_inf()->Self{$neg_inf}})*}}impl_inf!{i32,1_001_000_000,u32,1_001_000_000,f32,1e10,i64
            ,4_004_000_000_000_000_000,isize,4_004_000_000_000_000_000,u64,4_004_000_000_000_000_000,usize,4_004_000_000_000_000_000,f64,1e20,i128
            ,8_008_000_000_000_000_000_000_000_000_000_000_000,u128,8_008_000_000_000_000_000_000_000_000_000_000_000,}impl_neg_inf!{i32
            ,-1_001_000_000,u32,0,f32,-1e10,i64,-4_004_000_000_000_000_000,isize,-4_004_000_000_000_000_000,u64,0,usize,0,f64,-1e20,i128
            ,-8_008_000_000_000_000_000_000_000_000_000_000_000,u128,0,}}pub use inf::*;pub mod zero_one{use std::ops::{Add,Mul};pub trait Zero:Sized
            +Add<Output=Self>{fn zero()->Self;}pub trait One:Sized+Mul<Output=Self>{fn one()->Self;}macro_rules!impl_zero_one{($($t:ty),*)=>{$(impl 
            Zero for$t{fn zero()->Self{0 as$t}}impl One for$t{fn one()->Self{1 as$t}})*}}impl_zero_one!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128
            ,isize,f32,f64);}pub use zero_one::*;pub mod cast{pub trait Cast<T>{fn cast(self)->T;}macro_rules!impl_cast_2{($t1:ty,$($t2:ty),*)=>{$
            (impl Cast<$t2>for$t1{fn cast(self)->$t2{self as$t2}})*}}macro_rules!impl_cast_1{($($t:ty),*)=>{$(impl_cast_2!{$t,u8,u16,u32,u64,u128,i8
            ,i16,i32,i64,i128,usize,isize,f32,f64})*}}impl_cast_1!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize,f32,f64}}pub use cast::*;pub 
            mod numeric{use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Sub,SubAssign};use crate::__cargo_equip::crates
            ::__numeric_traits_0_1_0::zero_one;pub trait Numeric:Sized+Clone+Copy+std::fmt::Debug+std::fmt::Display+PartialEq+Add<Output=Self
            >+AddAssign+Sub<Output=Self>+SubAssign+Mul<Output=Self>+MulAssign+Div<Output=Self>+DivAssign+zero_one::Zero+zero_one
            ::One{}macro_rules!impl_numeric{($($t:ty),*)=>{$(impl Numeric for$t{})*};}impl_numeric!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize
            ,isize,f32,f64}}pub use numeric::*;pub mod integer{use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Rem,RemAssign
            ,Shl,ShlAssign,Shr,ShrAssign,};use crate::__cargo_equip::crates::__numeric_traits_0_1_0::Numeric;pub trait Integer:Numeric+Eq+Ord+std
            ::hash::Hash+Rem<Output=Self>+RemAssign+BitXor<Output=Self>+BitXorAssign+BitAnd<Output=Self>+BitAndAssign+BitOr<Output=Self>+BitOrAssign
            +Shl<usize,Output=Self>+ShlAssign<usize>+Shr<usize,Output=Self>+ShrAssign<usize>{fn popcount(self)->usize;fn msb_index(self)->usize;fn 
            lsb_index(self)->usize;fn msb(self)->Self;fn lsb(self)->Self;fn ceil_pow2(self)->Self;fn floor_pow2(self)->Self;fn ceil_log2(self)->usize
            ;fn floor_log2(self)->usize;fn checked_msb_index(self)->Option<usize>;fn checked_lsb_index(self)->Option<usize>;fn checked_ceil_pow2(self
            )->Option<Self>;fn checked_floor_pow2(self)->Option<Self>;fn checked_ceil_log2(self)->Option<usize>;fn checked_floor_log2(self)->Option
            <usize>;fn floor_div(self,other:Self)->Self;fn ceil_div(self,other:Self)->Self;fn gcd(self,other:Self)->Self;fn lcm(self,other:Self)->Self
            ;}macro_rules!impl_integer{($($t:ty),*)=>{$(impl Integer for$t{fn popcount(self)->usize{self.count_ones()as usize}fn msb_index(self
            )->usize{(<$t>::BITS-1-self.leading_zeros())as usize}fn lsb_index(self)->usize{self.trailing_zeros()as usize}fn msb(self)->Self{if self
            ==0{0}else{1<<self.msb_index()}}fn lsb(self)->Self{self&self.wrapping_neg()}fn ceil_pow2(self)->Self{1<<self.ceil_log2()}fn floor_pow2
            (self)->Self{assert!(self>0);self.msb()}fn ceil_log2(self)->usize{assert!(self>0);(<$t>::BITS-(self-1).leading_zeros())as usize}fn 
            floor_log2(self)->usize{assert!(self>0);self.msb_index()}fn checked_msb_index(self)->Option<usize>{if self==0{None}else{Some(self
            .msb_index())}}fn checked_lsb_index(self)->Option<usize>{if self==0{None}else{Some(self.lsb_index())}}fn checked_ceil_pow2(self)->Option
            <Self>{if self<=0{None}else{Some(self.ceil_pow2())}}fn checked_floor_pow2(self)->Option<Self>{if self<=0{None}else{Some(self.floor_pow2
            ())}}fn checked_ceil_log2(self)->Option<usize>{if self<=0{None}else{Some(self.ceil_log2())}}fn checked_floor_log2(self)->Option<usize>{if 
            self<=0{None}else{Some(self.floor_log2())}}#[allow(unused_comparisons)]fn floor_div(self,other:Self)->Self{self/other-if self^other
            <0&&self%other!=0{1}else{0}}#[allow(unused_comparisons)]fn ceil_div(self,other:Self)->Self{self/other+if self^other>=0&&self%other!
            =0{1}else{0}}#[allow(unused_comparisons)]fn gcd(self,other:Self)->Self{let mut x=if self<0{0-self}else{self};let mut y=if other<0{0
            -other}else{other};if x==0||y==0{return x|y;}let n=x.trailing_zeros();let m=y.trailing_zeros();x>>=n;y>>=m;while x!=y{if x>y{x-=y;x>>=x
            .trailing_zeros();}else{y-=x;y>>=y.trailing_zeros();}}x<<n.min(m)}fn lcm(self,other:Self)->Self{self/self.gcd(other)*other}})*}
            ;}impl_integer!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize}}pub use integer::*;pub mod signed{use std::ops::Neg;pub trait Signed
            :Sized+Neg<Output=Self>{fn signum(self)->Self;}macro_rules!impl_signed_integer{($($t:ty),*)=>{$(impl Signed for$t{fn signum(self
            )->Self{match self{n if n>0=>1,0=>0,_=>-1,}}})*};}macro_rules!impl_signed_float{($($t:ty),*)=>{$(impl Signed for$t{fn signum(self
            )->Self{if self.is_nan(){self}else if self==0.0{0.0}else if self>0.0{1.0}else{-1.0}}})*};}impl_signed_integer!{i8,i16,i32,i64,i128
            ,isize}impl_signed_float!{f32,f64}}pub use signed::*;pub trait Recip{fn recip(self)->Self;}impl Recip for f32{fn recip(self)->Self{self
            .recip()}}impl Recip for f64{fn recip(self)->Self{self.recip()}}}
    }
    pub(crate) mod macros {
        pub mod binary_optimization {}
        pub mod __max_flow_0_1_0 {}
        pub mod __numeric_traits_0_1_0 {}
    }
    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
    mod preludes {
        pub mod binary_optimization {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__max_flow_0_1_0 as max_flow;}
        pub mod __max_flow_0_1_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__numeric_traits_0_1_0 as numeric_traits;}
        pub mod __numeric_traits_0_1_0 {}
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX