結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-15 01:08:09
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 3,920 bytes
記録
コンパイル時間 12,594 ms
コンパイル使用メモリ 396,296 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-03 23:32:37
合計ジャッジ時間 15,772 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn main() -> std::io::Result<()> {
    use std::io::Write;
    let mut bw = std::io::BufWriter::new(std::io::stdout());
    input! { t: usize }
    for _ in 0..t {
        input! { n: i64, m: i64, a: i64, b: i64, c: i64, d: i64 }
        let ans = mwf(n, m, a, b, c, d);
        writeln!(bw, "{}", ans)?;
    }
    bw.flush()?;
    Ok(())
}

/**
 * Max Weighted Floor of Linear の計算 (n > 0, m > 0)
 * mwf(n, m, a, b, c, d) = max_{0 <= x < n} (a*x + b*floor((c*x+d)/m))
 */
fn mwf(mut n: i64, mut m: i64, mut a: i64, mut b: i64, mut c: i64, mut d: i64) -> i64 {
    assert!(n > 0 && m > 0);
    // 初回の正規化
    // c,d を m で割った余りに変換し、 a,b を更新、 sum_acc,max_acc を初期化
    // c,d が負の場合にも対応するため、ユークリッド除算を使う
    let q;
    (q, c) = (c.div_euclid(m), c.rem_euclid(m));
    a += b * q;
    let q;
    (q, d) = (d.div_euclid(m), d.rem_euclid(m));
    let mut sum_acc = b * q;
    let mut max_acc = sum_acc;
    // max(max_acc, sum_acc + mwf(n, m, a, b, c, d)) を不変量として維持して縮約
    loop {
        // 0 <= c < m, 0 <= d < m が保証される
        debug_assert!(0 <= c && c < m && 0 <= d && d < m);
        let n1 = n - 1;
        // 0 ≤ x < n における y = floor((c*x+d)/m) の最大値 y_max を計算
        let y_max = (c * n1 + d) / m;
        // 現在の小問題における x = 0, n-1 のときの値を max_acc に反映
        max_acc = max_acc.max(sum_acc).max(sum_acc + a * n1 + b * y_max);
        // x = 0, n-1 のいずれかで最大値を取るのが確定したら終了
        if y_max == 0 || (a >= 0 && b >= 0) || (a <= 0 && b <= 0) {
            return max_acc;
        }
        // 小問題へのパラメータ変換
        if a < 0 {
            sum_acc += a + b;
        }
        n = y_max;
        d = m - d - 1;
        std::mem::swap(&mut a, &mut b);
        std::mem::swap(&mut c, &mut m);
        // n,m > 0 は維持される、 c,d >= 0 も維持される
        debug_assert!(n > 0 && m > 0 && 0 <= c && 0 <= d);
        // 2回目以降の正規化
        // c,d を m で割った余りに変換し、a,b,sum_acc を更新
        // c,d,m は非負なので通常の剰余で良い
        let q;
        (q, c) = (c / m, c % m);
        a += b * q;
        let q;
        (q, d) = (d / m, d % m);
        sum_acc += b * q;
    }
}

use input_lite::*;
#[rustfmt::skip]#[allow(unused)]mod input_lite{#[macro_export]macro_rules!read_value{($b:expr,($($t:tt),*))=>{($(read_value!($b,$t)),*)};($b:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($b,$t)).collect::<Vec<_>>()};($b:expr,byte)=>{token($b,|s|s[0])};($b:expr,Bytes)=>{token($b,|s|s.to_vec())};($b:expr,Chars)=>{token($b,|s|std::str::from_utf8(s).unwrap().chars().collect::<Vec<_>>())};($b:expr,usize1)=>{read_value!($b,usize)-1};($b:expr,$t:ty)=>{token($b,|s|std::str::from_utf8(s).unwrap().parse::<$t>().unwrap())};}#[macro_export]macro_rules!input_inner{($b:expr)=>{};($b:expr,)=>{};($b:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($b,$t);input_inner!{$b$($r)*}};}#[macro_export]macro_rules!input{(source=$s:expr,$($r:tt)*)=>{input_inner!{$s,$($r)*}};($($r:tt)*)=>{let mut i=std::io::stdin().lock();input_inner!{&mut i,$($r)*}std::mem::drop(i);};}pub fn token<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->T)->T{let(b,mut l)=loop{let b=r.fill_buf().unwrap();assert!(!b.is_empty());if let Some(p)=b.iter().position(|&b|!b.is_ascii_whitespace()){break(&b[p..],p);}let l=b.len();r.consume(l);};if let Some(p)=b.iter().position(|&b|b.is_ascii_whitespace()){let t=&b[..p];let x=f(t);r.consume(l+p+1);return x;}l+=b.len();let mut t=b.to_vec();r.consume(l);while let Ok(b)=r.fill_buf(){if b.is_empty(){break;}if let Some(p)=b.iter().position(|&b|b.is_ascii_whitespace()){t.extend_from_slice(&b[..p]);r.consume(p+1);break;}let l=b.len();t.extend_from_slice(b);r.consume(l);}f(&t)}}
0