結果

問題 No.3509 Get More Money
コンテスト
ユーザー rhoo
提出日時 2026-03-21 12:03:55
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 190 ms / 2,000 ms
コード長 2,002 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,472 ms
コンパイル使用メモリ 196,528 KB
実行使用メモリ 25,164 KB
最終ジャッジ日時 2026-04-17 19:43:37
合計ジャッジ時間 15,028 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#[allow(non_snake_case)]


// day iにジュエルをx個残したときの最大利益は区分線形凸関数になる
// 遷移は 傾きA_i,長さB_iの線分と傾きC_i,長さD_iの線分を挿入してから
// 前から長さD_i削り、後ろからB_i削るかんじになる
// 最小値削除,最大値削除,追加が高速にできればいい
// BinaryHeapを２つ使って管理


fn main(){
    use proconio::*;
    input!{
        t:usize,
    }

    use itertools::*;
    use std::cmp::Reverse as Rev;
    use std::collections::BinaryHeap as Heap;

    let solve=||{
        input!{
            n:usize,
            K:i64,
            A:[i64;n],
            B:[i64;n],
            C:[i64;n],
            D:[i64;n],
        }

        let mut len=vec![K];
        let mut minQ=Heap::from([(Rev(1e9 as i64),0)]);
        let mut maxQ=Heap::from([(1e9 as i64,0)]);
        let mut Z=0; // 定数項

        for (a,b,c,d) in izip!(A,B,C,D){
            minQ.push((Rev(a),len.len()));
            maxQ.push((a,len.len()));
            len.push(b);

            minQ.push((Rev(c),len.len()));
            maxQ.push((c,len.len()));
            len.push(d);
            Z-=c*d;

            // 後ろからb削る
            let mut rem=b;
            while rem!=0{
                let &(_,id)=maxQ.peek().unwrap();
                let sub=rem.min(len[id]);
                rem-=sub;
                len[id]-=sub;
                if len[id]==0{
                    maxQ.pop().unwrap();
                }
            }

            // 前からd削る
            let mut rem=d;
            while rem!=0{
                let &(Rev(coeff),id)=minQ.peek().unwrap();
                let sub=rem.min(len[id]);
                rem-=sub;
                len[id]-=sub;
                if len[id]==0{
                    minQ.pop().unwrap();
                }
                Z+=coeff*sub;
            }
        }

        print!("{}\n",-Z);
    };
    
    for _ in 0..t{
        solve();
    }
}
0