結果

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

ソースコード

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));
    if l > r {
        return i128::MIN;
    }
    let f = |x: i128| a * x + b * ((c * x + d).div_euclid(m));
    if c < 0 {
        //print!("C<0 -> ");
        return solve([l, r, m, a, -b, -c, -d + m - 1]);
    }
    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 a < 0 {
        let mut new_l = (c * l + d).div_euclid(m);
        let mut new_r = (c * r + d).div_euclid(m);
        let mut max = i128::MIN;
        //print!("A<0 -> ");
        let g = |y: i128| (m * y - d + c - 1).div_euclid(c);
        if g(new_l) < l {
            new_l += 1;
            max = max.max(f(l));
        }
        if g(new_r) > r {
            new_r -= 1;
            max = max.max(f(r));
        }
        return max.max(solve([new_l, new_r, c, b, a, m, -d + c - 1]));
    } else {
        let mut new_l = (c * l + d).div_euclid(m);
        let mut new_r = (c * r + d).div_euclid(m);
        let mut max = i128::MIN;
        //print!("A>0 -> ");
        let g = |y: i128| (m * y + m - d - 1).div_euclid(c);
        if g(new_l) < l {
            new_l += 1;
            max = max.max(f(l));
        }
        if g(new_r) > r {
            new_r -= 1;
            max = max.max(f(r));
        }
        return max.max(solve([new_l, new_r, c, b, a, m, m - d - 1]));
    }
}
0