結果

問題 No.2713 Just Solitaire
ユーザー 37kt
提出日時 2025-03-20 08:17:38
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 16,137 bytes
コンパイル時間 25,170 ms
コンパイル使用メモリ 400,232 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-20 08:18:05
合計ジャッジ時間 17,074 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 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_unary(i, |bi| Some([0, a[i]][bi]));
    }
    for i in 0..m {
        opt.add_if_all_1(&c[i], -b[i]);
    }

    let (cost, choice) = opt.solve();
    let mut sum = 0;
    for i in 0..n {
        if choice[i] == 1 {
            sum += a[i];
        }
    }
    for i in 0..m {
        if c[i].iter().all(|&j| choice[j] == 1) {
            sum -= b[i];
        }
    }
    assert_eq!(cost, sum);

    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_nullary(&mut self,cost:i64){self.cost_0=self.cost_0.saturating_add(cost);}pub fn add_unary(&mut self,i:usize,mut cost:impl FnMut(usize)->Option<i64>){for bi in 0..2{let x=cost(bi).unwrap_or(i64::MAX);self.cost_1[i][bi]=self.cost_1[i][bi].saturating_add(x);}}pub fn add_binary(&mut self,i:usize,j:usize,mut cost:impl FnMut(usize,usize)->Option<i64>,){const INF:i64=1<<40;let cost:[[i64;2];2]=std::array::from_fn(|bi|std::array::from_fn(|bj|cost(bi,bj).unwrap_or(INF)));let x=cost[0][1]+cost[1][0]-cost[0][0]-cost[1][1];assert!(x>=0,"Monge property is violated");self.add_nullary(cost[0][0]);self.add_unary(i,|bi|Some([0,cost[1][0]-cost[0][0]][bi]));self.add_unary(j,|bj|Some([0,cost[1][1]-cost[1][0]][bj]));self.add_edge(i,j,x);}pub fn add_ternary(&mut self,_i:usize,_j:usize,_k:usize,mut _cost:impl FnMut(usize,usize,usize)->i64,){todo!()}pub fn add_if_all_0<I>(&mut self,items:I,cost:i64)where I:IntoIterator,I::Item:Borrow<usize>,{if cost==0{return;}let mut items=items.into_iter().map(|x|*x.borrow()).collect::<Vec<_>>();items.sort_unstable();items.dedup();assert!(items.len()<2||cost<=0,"if items.len() >= 2, cost must be non-positive");match&items[..]{[]=>self.add_nullary(cost),&[i]=>self.add_unary(i,|bi|Some([cost,0][bi])),&[i,j]=>self.add_binary(i,j,|bi,bj|Some([[cost,0],[0,0]][bi][bj])),items=>{self.add_nullary(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_if_all_1<I>(&mut self,items:I,cost:i64)where I:IntoIterator,I::Item:Borrow<usize>,{if cost==0{return;}let mut items=items.into_iter().map(|x|*x.borrow()).collect::<Vec<_>>();items.sort_unstable();items.dedup();assert!(items.len()<2||cost<=0,"if items.len() >= 2, cost must be non-positive");match&items[..]{[]=>self.add_nullary(cost),&[i]=>self.add_unary(i,|bi|Some([0,cost][bi])),&[i,j]=>self.add_binary(i,j,|bi,bj|Some([[0,0],[0,cost]][bi][bj])),items=>{self.add_nullary(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_if_any_0<I>(&mut self,items:I,cost:i64)where I:IntoIterator,I::Item:Borrow<usize>,{self.add_nullary(cost);self.add_if_all_1(items,-cost);}pub fn add_if_any_1<I>(&mut self,items:I,cost:i64)where I:IntoIterator,I::Item:Borrow<usize>,{self.add_nullary(cost);self.add_if_all_0(items,-cost);}pub fn solve(&mut self)->(i64,Vec<usize>){for(i,cost)in std::mem::take(&mut self.cost_1).into_iter().enumerate(){if cost[0]<cost[1]{self.add_nullary(cost[0]);self.add_edge(self.src,i,cost[1].saturating_sub(cost[0]));}else{self.add_nullary(cost[1]);self.add_edge(i,self.dst,cost[0].saturating_sub(cost[1]));}}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.saturating_add(flow.max_flow(self.src,self.dst,None));let mut cut=flow.min_cut();cut.truncate(self.n_item);(cost,cut)}fn add_edge(&mut self,i:usize,j:usize,cost:i64){assert!(cost>=0);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::Integer;mod graph{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,pub(in crate::__cargo_equip::crates::__max_flow_0_1_0)rev:usize,}}mod queue{use crate::__cargo_equip::preludes::__max_flow_0_1_0::*;#[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<Vec<graph::Edge>>,pos:Vec<(usize,usize)>,iter:Vec<usize>,dist:Vec<u64>,queue:queue::Queue,zero:u64,src:Option<usize>,}#[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![],pos:vec![],iter:vec![],dist:vec![],queue:queue::Queue::new(),zero:1<<60,src:None,}}pub fn num_vertices(&self)->usize{self.edges.len()}pub fn num_edges(&self)->usize{self.pos.len()}pub fn add_vertex(&mut self)->usize{self.src=None;let v=self.edges.len();self.edges.push(vec![]);self.iter.push(0);self.dist.push(self.zero);v}pub fn add_vertices(&mut self,n:usize)->Vec<usize>{self.src=None;let v=self.edges.len();self.edges.resize(v+n,vec![]);self.iter.resize(v+n,0);self.dist.resize(v+n,self.zero);(v..v+n).collect()}pub fn add_edge(&mut self,src:usize,dst:usize,cap:i64)->usize{assert!(src<self.num_vertices());assert!(dst<self.num_vertices());assert!(cap>=0);self.src=None;let e=self.pos.len();let i=self.edges[src].len();let j=self.edges[dst].len()+if src==dst{1}else{0};self.edges[src].push(graph::Edge{dst,cap,rev:j});self.edges[dst].push(graph::Edge{dst:src,cap:0,rev:i,});self.pos.push((src,i));e}pub fn edge(&self,e:usize)->Edge{let(src,i)=self.pos[e];let e1=self.edges[src][i];let e2=self.edges[e1.dst][e1.rev];Edge{src,dst:e1.dst,cap:e1.cap+e2.cap,flow:e2.cap,}}pub fn edges(&self,)->impl Iterator<Item=Edge>+DoubleEndedIterator+ExactSizeIterator+FusedIterator+'_{(0..self.num_edges()).map(|e|self.edge(e))}pub fn max_flow(&mut self,src:usize,dst:usize,limit:Option<i64>)->i64{assert!(src!=dst);assert!(src<self.num_vertices());assert!(dst<self.num_vertices());self.src=Some(src);let limit=limit.unwrap_or(i64::MAX);let max_cap=self.edges.iter().flatten().map(|e|e.cap).max().unwrap_or(0);if max_cap==0{return 0;}let mut flow=0;for f in(0..=limit.min(max_cap).floor_log2()).map(|i|1<<i).rev(){while flow<=limit-f&&self.build_augmenting_path(src,dst,f){self.iter.fill(0);flow+=self.find_augmenting_path(src,dst,f,limit-flow);}}flow}pub fn min_cut(&mut self)->Vec<usize>{let src=self.src.expect("max_flow is not called");let mut res=vec![1;self.num_vertices()];self.queue.clear();self.queue.set_capacity(self.num_vertices());res[src]=0;self.queue.push(src);while let Some(v)=self.queue.pop(){for e in&self.edges[v]{if e.cap>0&&res[e.dst]==1{res[e.dst]=0;self.queue.push(e.dst);}}}res}fn build_augmenting_path(&mut self,src:usize,dst:usize,base:i64)->bool{self.zero-=1<<30;self.queue.clear();self.queue.set_capacity(self.num_vertices());self.dist[src]=self.zero;self.queue.push(src);while let Some(v)=self.queue.pop(){for e in&self.edges[v]{if e.cap>=base&&self.dist[e.dst]>self.dist[v]+1{self.dist[e.dst]=self.dist[v]+1;self.queue.push(e.dst);if e.dst==dst{return true;}}}}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]<self.edges[v].len(){let e=self.edges[v][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[v][self.iter[v]].cap-=diff;self.edges[e.dst][e.rev].cap+=diff;sum+=diff;if flow-sum<base{break;}}}self.iter[v]+=1;}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 {}
    }
}
0