#1130065 (Rust) No.3322 引っ張りだこ

• 問題: No.3322 引っ張りだこ
• ユーザー: akakimidori
• 提出日時: 2025-10-31 21:47:55
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 246 ms / 2,000 ms
• コード長: 5,446 bytes
• コンパイル時間: 14,751 ms
• コンパイル使用メモリ: 398,108 KB
• 実行使用メモリ: 9,088 KB
• 最終ジャッジ日時: 2025-10-31 21:48:17
• 合計ジャッジ時間: 19,648 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 43

コンパイルメッセージ

warning: unused variable: `p`
   --> src/main.rs:106:17
    |
106 |             let p = eval(r);
    |                 ^ help: if this is intentional, prefix it with an underscore: `_p`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: function `naive` is never used
  --> src/main.rs:26:4
   |
26 | fn naive(a: Vec<i64>, b: Vec<i64>, k: usize) -> i64 {
   |    ^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: function `rand_memory` is never used
   --> src/main.rs:174:4
    |
174 | fn rand_memory() -> usize {
    |    ^^^^^^^^^^^

warning: function `rand` is never used
   --> src/main.rs:178:4
    |
178 | fn rand() -> usize {
    |    ^^^^

warning: function `shuffle` is never used
   --> src/main.rs:191:4
    |
191 | fn shuffle<T>(a: &mut [T]) {
    |    ^^^^^^^

ソースコード

// K 以下
// どうせ凸って思ってたがそうじゃねえらしい
// mod 2 で凸？

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let t: u32 = sc.next();
    for _ in 0..t {
        let n: usize = sc.next();
        let k: usize = sc.next();
        let a: Vec<i64> = sc.next_vec(n);
        let b: Vec<i64> = sc.next_vec(n);
        let ans = solve(a, b, k);
        writeln!(out, "{}", ans).ok();
        /*
        let n: usize = 10;
        let k: usize = rand() % (n + 1);
        let a: Vec<i64> = (0..n).map(|_| (rand() % 10 + 1) as i64).collect();
        let b: Vec<i64> = (0..n).map(|_| (rand() % 10 + 1) as i64).collect();
        let res = naive(a.clone(), b.clone(), k);
        let ans = solve(a.clone(), b.clone(), k);
        assert_eq!(res, ans, "{:?} {:?} {k}", a, b);
        */
    }
}

fn naive(a: Vec<i64>, b: Vec<i64>, k: usize) -> i64 {
    let inf = std::i64::MAX / 2;
    let mut dp = vec![[-inf; 2]];
    dp[0][0] = 0;
    for (&a, &b) in a.iter().zip(b.iter()) {
        let mut next = vec![[-inf; 2]; dp.len() + 1];
        for (i, dp) in dp.iter().enumerate() {
            for (j, dp) in dp.iter().enumerate() {
                next[i][j].chmax(*dp);
                next[i + 1][j ^ 1].chmax(*dp);
            }
        }
        dp = next;
        for dp in dp.iter_mut() {
            dp[0] += a;
            dp[1] += b;
        }
    }
    println!(
        "{:?}",
        dp.iter().map(|dp| dp[0]).step_by(2).collect::<Vec<_>>()
    );
    println!(
        "{:?}",
        dp.iter()
            .map(|dp| dp[1])
            .skip(1)
            .step_by(2)
            .collect::<Vec<_>>()
    );
    let dp = dp.into_iter().map(|p| p[0].max(p[1])).collect::<Vec<_>>();
    println!("val] {:?}", dp);
    println!(
        "{:?}",
        dp.windows(2).map(|dp| dp[1] - dp[0]).collect::<Vec<_>>()
    );
    dp.into_iter().take(k + 1).max().unwrap()
}

fn solve(a: Vec<i64>, b: Vec<i64>, k: usize) -> i64 {
    let inf = std::i64::MAX / 2 - 1;
    let a = a.into_iter().map(|a| 2 * a).collect::<Vec<_>>();
    let b = b.into_iter().map(|b| 2 * b).collect::<Vec<_>>();
    let mut ans = -inf;
    for i in 0..2 {
        if i == 1 && k == 0 {
            continue;
        }
        let k = if k % 2 == i {k} else {k - 1} as i32;
        let eval = |m: i64| -> (i64, i32) {
            let mut dp = [(-inf, 0); 2];
            dp[0] = (0, 0);
            for (&a, &b) in a.iter().zip(b.iter()) {
                let mut next = [(-inf, 0); 2];
                for (i, dp) in dp.iter().enumerate() {
                    next[i].chmax(*dp);
                    next[i ^ 1].chmax((dp.0 - m, dp.1 - 1));
                }
                next[0].0 += a;
                next[1].0 += b;
                dp = next;
            }
            dp[i]
        };
        if -eval(0).1 <= k {
            ans.chmax(eval(0).0);
            continue;
        }
        let mut l = -1;
        let mut r = inf;
        while r - l > 1 {
            let m = (l + r) / 2;
            if -eval(m).1 > k {
                l = m;
            } else {
                r = m;
            }
        }
        //println!("alien {i} {r} {:?}", eval(r));
        if i == 0 || k > 0 {
            let p = eval(r);
            ans.chmax(eval(r).0 + k as i64 * r);
        }
    }
    ans / 2
}

// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
    fn chmin(&mut self, x: Self) -> bool;
    fn chmax(&mut self, x: Self) -> bool;
}

impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, x: Self) -> bool {
        *self > x && {
            *self = x;
            true
        }
    }
    fn chmax(&mut self, x: Self) -> bool {
        *self < x && {
            *self = x;
            true
        }
    }
}
// ---------- end chmin, chmax ----------
fn rand_memory() -> usize {
    Box::into_raw(Box::new("I hope this is a random number")) as usize
}

fn rand() -> usize {
    static mut X: usize = 0;
    unsafe {
        if X == 0 {
            X = rand_memory();
        }
        X ^= X << 13;
        X ^= X >> 17;
        X ^= X << 5;
        X
    }
}

fn shuffle<T>(a: &mut [T]) {
    for i in 1..a.len() {
        let p = rand() % (i + 1);
        a.swap(i, p);
    }
}