#1152663 (Rust) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: rhoo
• 提出日時: 2026-03-16 18:41:12
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: TLE
• 実行時間: -
• コード長: 11,172 bytes
• コンパイル時間: 1,793 ms
• コンパイル使用メモリ: 200,112 KB
• 実行使用メモリ: 81,456 KB
• 最終ジャッジ日時: 2026-04-17 19:38:34
• 合計ジャッジ時間: 15,948 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_1

ファイルパターン	結果
sample	-- * 1
other	TLE * 1 -- * 59

ソースコード

#![allow(non_snake_case,dead_code)]



fn main(){
    proconio::input!{
        t:usize,
    }
    for _ in 0..t{
        solve();
    }
}



fn solve(){
    proconio::input!{
        n:usize,
        k:i64,
        a:[i64;n],
        b:[i64;n],
        c:[i64;n],
        d:[i64;n],
    }

    let mut g=NetworkSimplex::new(n+2);
    let source=n;
    let sink=n+1;
    
    for i in 0..n{
        g.add_edge(source,i,0,b[i],a[i]);
        g.add_edge(i,sink,0,d[i],-c[i]);
        
        if 0<i{
            g.add_edge(i-1,i,0,k,0);
        }
    }

    let flow=b.iter().sum::<i64>();
    g.add_edge(source,sink,0,flow,0);

    g.add_excess(source,flow);
    g.add_excess(sink,-flow);
    let res=network_simplex(g);

    println!("{}",-res.cost);
}



// https://github.com/yosupo06/yosupo-library/blob/main/src/yosupo/networksimplex.hpp ここからパクりました
// 負辺ok
mod network_simplex{
    #[derive(Clone,Copy,Debug)]
    struct Edge{
        to:usize,
        cap:i64,
        cost:i64,
    }

    pub struct NetworkSimplex{
        n:usize,
        edges:Vec<Edge>,
        lowers:Vec<i64>,
        excess:Vec<i64>,
    }
    impl NetworkSimplex{
        pub fn new(n:usize)->Self{
            Self{
                n,
                edges:vec![],
                lowers:vec![],
                excess:vec![0;n],
            }
        }

        pub fn add_excess(&mut self,v:usize,ex:i64){
            self.excess[v]+=ex;
        }

        pub fn add_edge(&mut self,u:usize,v:usize,lower:i64,upper:i64,cost:i64){
            let new=Edge{to:v,cap:upper-lower,cost};
            self.edges.push(new);
            let new=Edge{to:u,cap:0,cost:-cost};
            self.edges.push(new);
            self.excess[u]-=lower;
            self.excess[v]+=lower;
            self.lowers.push(lower);
        }
    }

    pub struct FlowResult{
        pub feasible:bool,
        pub cost:i128,
        pub flow:Vec<i64>,
        pub pot:Vec<i64>,
    }

    #[derive(Clone,Copy)]
    struct Parent{
        p:usize,
        e:usize,
        up:i64,
        down:i64,
    }

    pub fn network_simplex(g:NetworkSimplex)->FlowResult{
        let mut edges=g.edges;
        let excess=g.excess;
        let n=g.n;
        let m=edges.len();
        
        let mut pot=vec![0;n+1];
        let mut art_cost=1;
        for i in (0..m).step_by(2){
            art_cost+=edges[i].cost.abs();
        }

        let mut parents=vec![Parent{p:0,e:0,up:0,down:0};n];

        for i in 0..n{
            if excess[i]>=0{
                edges.push(Edge{to:n,cap:0,cost:art_cost});
                edges.push(Edge{to:i,cap:excess[i],cost:-art_cost});
                pot[i]=-art_cost;
            } else{
                edges.push(Edge{to:n,cap:-excess[i],cost:-art_cost});
                edges.push(Edge{to:i,cap:0,cost:art_cost});
                pot[i]=art_cost;
            }
            parents[i].p=n;
            parents[i].e=edges.len()-2;
            parents[i].up=edges[parents[i].e].cap;
            parents[i].down=edges[parents[i].e^1].cap;
        }

        let mut depth=vec![1;n+1];
        depth[n]=0;

        let mut next=vec![0;2*(n+1)];
        let mut prev=vec![0;2*(n+1)];

        let conn=|a:usize,b:usize,next_vec:&mut [usize],prev_vec:&mut [usize]|{
            next_vec[a]=b;
            prev_vec[b]=a;
        };

        for i in 0..=n{
            conn(2*i,2*i+1,&mut next,&mut prev);
        }
        for i in 0..n{
            let n_2n=next[2*n];
            conn(2*i+1,n_2n,&mut next,&mut prev);
            conn(2*n,2*i,&mut next,&mut prev);
        }

        fn push_flow(ei0:usize,edges:&mut [Edge],pot:&mut [i64],parents:&mut [Parent],depth:&mut [i32],next:&mut [usize],prev:&mut [usize]){
            let u0=edges[ei0^1].to;
            let v0=edges[ei0].to;
            let cycle_len=edges[ei0].cost+pot[u0]-pot[v0];

            let mut flow=edges[ei0].cap;
            let mut del_u_side=true;
            let mut del_u=v0;

            let lca={
                let u=u0;
                let v=v0;
                
                let mut u_curr=u;
                let mut v_curr=v;
                
                while depth[u_curr]>depth[v_curr]{
                    if parents[u_curr].down<flow{
                        flow=parents[u_curr].down;
                        del_u=u_curr;
                        del_u_side=true;
                    }
                    u_curr=parents[u_curr].p;
                }
                while depth[v_curr]>depth[u_curr]{
                    if parents[v_curr].up<=flow{
                        flow=parents[v_curr].up;
                        del_u=v_curr;
                        del_u_side=false;
                    }
                    v_curr=parents[v_curr].p;
                }
                
                while u_curr!=v_curr{
                    if parents[u_curr].down<flow{
                        flow=parents[u_curr].down;
                        del_u=u_curr;
                        del_u_side=true;
                    }
                    u_curr=parents[u_curr].p;

                    if parents[v_curr].up<=flow{
                        flow=parents[v_curr].up;
                        del_u=v_curr;
                        del_u_side=false;
                    }
                    v_curr=parents[v_curr].p;
                }
                u_curr
            };

            if flow>0{
                let mut u=u0;
                while u!=lca{
                    parents[u].up+=flow;
                    parents[u].down-=flow;
                    u=parents[u].p;
                }
                let mut v=v0;
                while v!=lca{
                    parents[v].up-=flow;
                    parents[v].down+=flow;
                    v=parents[v].p;
                }
            }

            let mut u=u0;
            let mut par=v0;
            let mut p_diff=-cycle_len;
            let mut p_caps_first=edges[ei0].cap-flow;
            let mut p_caps_second=edges[ei0^1].cap+flow;

            if !del_u_side{
                std::mem::swap(&mut u,&mut par);
                std::mem::swap(&mut p_caps_first,&mut p_caps_second);
                p_diff*=-1;
            }
            let mut par_e=ei0^(!del_u_side) as usize;

            while par!=del_u{
                let mut d=depth[par];
                let mut idx=2*u;
                while idx!=2*u+1{
                    if idx%2==0{
                        d+=1;
                        let node_idx=idx/2;
                        pot[node_idx]+=p_diff;
                        depth[node_idx]=d;
                    } else{
                        d-=1;
                    }
                    idx=next[idx];
                }

                let prev_2u=prev[2*u];
                let next_2u1=next[2*u+1];
                next[prev_2u]=next_2u1;
                prev[next_2u1]=prev_2u;

                let next_2par=next[2*par];
                next[2*u+1]=next_2par;
                prev[next_2par]=2*u+1;

                next[2*par]=2*u;
                prev[2*u]=2*par;

                std::mem::swap(&mut parents[u].e,&mut par_e);
                par_e^=1;

                std::mem::swap(&mut parents[u].up,&mut p_caps_first);
                std::mem::swap(&mut parents[u].down,&mut p_caps_second);
                std::mem::swap(&mut p_caps_first,&mut p_caps_second);

                let next_u=parents[u].p;
                parents[u].p=par;
                par=u;
                u=next_u;
            }
            edges[par_e].cap=p_caps_first;
            edges[par_e^1].cap=p_caps_second;
        }

        // Pivot Rule constants
        let list_length=10.max((0.2*(m as f64).sqrt()).round() as usize);
        let minor_limit=3.max((0.1*(list_length as f64)).round() as usize);
        let mut candidates=Vec::with_capacity(list_length);

        let mut ei=0;
        loop{
            for _ in 0..minor_limit{
                if candidates.is_empty(){
                    break;
                }
                let mut best=0;
                let mut best_ei=!0;

                let mut i=0;
                while i<candidates.len(){
                    let cei:usize=candidates[i];
                    if edges[cei].cap==0{
                        let last=candidates.len()-1;
                        candidates.swap(i,last);
                        candidates.pop();
                        continue;
                    }
                    let c_len=edges[cei].cost+pot[edges[cei^1].to]-pot[edges[cei].to];
                    if c_len>=0{
                        let last=candidates.len()-1;
                        candidates.swap(i,last);
                        candidates.pop();
                        continue;
                    }

                    if c_len<best{
                        best=c_len;
                        best_ei=cei;
                    }
                    i+=1;
                }

                if best_ei==!0{
                    break;
                }
                push_flow(best_ei,&mut edges,&mut pot,&mut parents,&mut depth,&mut next,&mut prev);
            }

            let mut best=0;
            let mut best_ei=!0;

            candidates.clear();
            let edges_len=edges.len();
            for _ in 0..edges_len{
                if edges[ei].cap>0{
                    let clen=edges[ei].cost+pot[edges[ei^1].to]-pot[edges[ei].to];
                    if clen<0{
                        if clen<best{
                            best=clen;
                            best_ei=ei;
                        }
                        candidates.push(ei);
                        if candidates.len()==list_length{
                            break;
                        }
                    }
                }

                ei+=1;
                if ei==edges_len{
                    ei=0;
                }
            }

            if candidates.is_empty(){
                break;
            }
            push_flow(best_ei,&mut edges,&mut pot,&mut parents,&mut depth,&mut next,&mut prev);
        }

        // Finalize
        for i in 0..n{
            edges[parents[i].e].cap=parents[i].up;
            edges[parents[i].e^1].cap=parents[i].down;
        }

        let mut feasible=true;
        for i in 0..n{
            if excess[i]>=0{
                if edges[m+2*i+1].cap>0{
                    feasible=false;
                    break;
                }
            } else{
                if edges[m+2*i].cap>0{
                    feasible=false;
                    break;
                }
            }
        }

        if !feasible{
            return FlowResult{feasible:false,cost:0,flow:vec![],pot:vec![]};
        }

        let mut total_cost=0;
        let mut flow=Vec::with_capacity(m/2);
        for i in (0..m).step_by(2){
            let f=g.lowers[i/2]+edges[i^1].cap;
            flow.push(f);
            total_cost+=f as i128*edges[i].cost as i128;
        }
        pot.pop();

        FlowResult{
            feasible:true,
            cost:total_cost,
            flow,pot,
        }
    }
}
use network_simplex::*;