結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー cacampu
提出日時 2025-12-04 18:01:04
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,068 bytes
記録
コンパイル時間 12,455 ms
コンパイル使用メモリ 402,844 KB
実行使用メモリ 21,456 KB
最終ジャッジ日時 2025-12-04 18:01:28
合計ジャッジ時間 22,708 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 2 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
fn main() {
    input! {
        t:usize,
        dat:[[i128;6];t]
    }
    for d in dat {
        let [n, m, a, b, c, d] = d[..] else {
            unreachable!()
        };
        let ans = solve([0, n - 1, m, a, b, c, d]);
        println!("{}", ans);
    }
}
fn _naive(dat: [i64; 7]) -> i64 {
    let [l, r, m, a, b, c, d] = dat;
    let f = |x: i64| a * x + b * ((c * x + d).div_euclid(m));
    (l..=r).map(f).max().unwrap()
}
fn solve(dat: [i128; 7]) -> i128 {
    let [l, r, m, a, b, c, d] = dat;
    //println!(
    //    "[{}, {}] f(x) = {}x + {} [({}x + {})/{}]",
    //    l, r, a, b, c, d, m
    //);
    //println!("naive_ans : {}", naive(dat));
    let f = |x: i128| a * x + b * ((c * x + d).div_euclid(m));
    if c >= m || d >= m || d < 0 {
        let k = c / m;
        let d_m = d.div_euclid(m);
        let a = a + b * k;
        let c = c % m;
        let d = d.rem_euclid(m);
        //print!("C>=m -> {} + ", d_m * b);
        return d_m * b + solve([l, r, m, a, b, c, d]);
    }
    if a * b * c >= 0 || (c.abs() < m && a.abs() >= b.abs()) {
        //print!(" base");
        return f(l).max(f(r));
    }
    if c < 0 {
        //print!("C<0 -> ");
        return solve([l, r, m, a, -b, -c, -d + m - 1]);
    }
    if a < 0 {
        let new_l = (c * l + d).div_euclid(m);
        let new_r = (c * r + d).div_euclid(m);
        //print!("A<0 -> ");
        if (m * new_l - d + c - 1).div_euclid(c) < l {
            //print!("max {}", f(l));
            return f(l).max(solve([new_l + 1, new_r, c, b, a, m, -d + c - 1]));
        } else {
            return solve([new_l, new_r, c, b, a, m, -d + c - 1]);
        }
    } else {
        let new_l = (c * l + d).div_euclid(m);
        let new_r = (c * r + d).div_euclid(m);
        //print!("A>0 -> ");
        if (m * new_l + m - d - 1).div_euclid(c) < l {
            //print!("max {}", f(l));
            return f(l).max(solve([new_l, new_r, c, b, a, m, m - d - 1]));
        } else {
            return solve([new_l, new_r, c, b, a, m, m - d - 1]);
        }
    }
}
0