結果

問題 No.2741 Balanced Choice
ユーザー Yukino DX.Yukino DX.
提出日時 2024-04-29 17:25:36
言語 Rust
(1.77.0)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 3,318 bytes
コンパイル時間 11,833 ms
コンパイル使用メモリ 380,488 KB
実行使用メモリ 197,888 KB
最終ジャッジ日時 2024-04-29 17:25:54
合計ジャッジ時間 14,890 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 231 ms
197,888 KB
testcase_01 AC 227 ms
197,888 KB
testcase_02 AC 222 ms
197,888 KB
testcase_03 AC 227 ms
197,888 KB
testcase_04 AC 247 ms
197,888 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 141 ms
128,384 KB
testcase_08 AC 194 ms
175,360 KB
testcase_09 AC 135 ms
121,984 KB
testcase_10 AC 156 ms
139,776 KB
testcase_11 AC 210 ms
176,512 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports)]
//use itertools::{iproduct, Itertools};
use proconio::input;
use proconio::marker::*;
use std::collections::*;

fn main() {
    input! {
        n:usize,
        w:usize,
        d:usize,
        twvs:[(usize,usize,i64);n],
    }

    let twv = [
        twvs.iter()
            .filter(|(t, _, _)| *t == 0)
            .copied()
            .collect::<Vec<_>>(),
        twvs.iter()
            .filter(|(t, _, _)| *t == 1)
            .copied()
            .collect::<Vec<_>>(),
    ];

    const INF: i64 = std::i64::MAX;
    let mut dp = [
        vec![vec![-INF; w + 1]; twv[0].len() + 1],
        vec![vec![-INF; w + 1]; twv[1].len() + 1],
    ];
    dp[0][0][0] = 0;
    dp[1][0][0] = 0;
    for k in 0..2 {
        for i in 0..twv[k].len() {
            for j in 0..=w {
                if dp[k][i][j] == -INF {
                    continue;
                }

                dp[k][i + 1][j] = dp[k][i + 1][j].max(dp[k][i][j]);
                if j + twv[k][i].1 <= w {
                    dp[k][i + 1][j + twv[k][i].1] =
                        dp[k][i + 1][j + twv[k][i].1].max(dp[k][i][j] + twv[k][i].2);
                }
            }
        }
    }

    let mut seg = SegmentTree::new(w + 1, |a, b| a.max(b), |_, new| new, -INF);
    for i in 0..=w {
        seg.update(i, dp[1][twv[1].len()][i]);
    }

    let mut ans = 0;
    for i in 0..=w {
        if dp[0][twv[0].len()][i] == -INF {
            continue;
        }

        let left = i.saturating_sub(d);
        let right = (w - i).min(i + d);
        if left > right {
            continue;
        }

        let score = dp[0][twv[0].len()][i] + seg.query(left, right + 1);
        ans = ans.max(score);
    }

    println!("{}", ans);
}

use segmenttree::*;
mod segmenttree {
    pub struct SegmentTree<T, F: Fn(T, T) -> T, G: Fn(T, T) -> T> {
        n: usize,
        merge: F,
        replace: G,
        unit: T,
        tree: Vec<T>,
    }

    impl<T, F, G> SegmentTree<T, F, G>
    where
        T: Copy,
        F: Fn(T, T) -> T,
        G: Fn(T, T) -> T,
    {
        pub fn new(len: usize, merge: F, replace: G, unit: T) -> Self {
            let mut n = 1;
            while n < len {
                n *= 2;
            }
            Self {
                n,
                merge,
                replace,
                unit,
                tree: vec![unit; 2 * n],
            }
        }

        //0index
        pub fn update(&mut self, mut i: usize, x: T) {
            i += self.n - 1;
            self.tree[i] = (self.replace)(self.tree[i], x);
            while i > 0 {
                i = (i - 1) / 2;
                self.tree[i] = (self.merge)(self.tree[2 * i + 1], self.tree[2 * i + 2]);
            }
        }

        //[l,r)
        pub fn query(&self, l: usize, r: usize) -> T {
            self._query(l, r, 0, 0, self.n)
        }

        fn _query(&self, l: usize, r: usize, i: usize, a: usize, b: usize) -> T {
            if r <= a || b <= l {
                return self.unit;
            }

            if l <= a && b <= r {
                return self.tree[i];
            }

            let res0 = self._query(l, r, 2 * i + 1, a, (a + b) / 2);
            let res1 = self._query(l, r, 2 * i + 2, (a + b) / 2, b);
            (self.merge)(res0, res1)
        }
    }
}
0