結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-27 12:50:27
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 280 ms / 2,000 ms
コード長 3,896 bytes
記録
コンパイル時間 13,955 ms
コンパイル使用メモリ 397,204 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-03 23:34:45
合計ジャッジ時間 17,177 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: i128, m: i128, a: i128, b: i128, c: i128, d: i128 }
        let ans = mwf(0, n, m, a, b, c, d);
        writeln!(bw, "{}", ans)?;
    }
    bw.flush()?;
    Ok(())
}

fn divrem_euclid<T>(x: T, y: T) -> (T, T)
where
    T: Copy
        + Ord
        + std::ops::Add<Output = T>
        + std::ops::Sub<Output = T>
        + std::ops::Div<Output = T>
        + std::ops::Rem<Output = T>
        + From<i8>,
{
    let zero = T::from(0);
    let one = T::from(1);
    let (mut q, mut r) = (x / y, x % y);
    if r < zero {
        if y > zero {
            q = q - one;
            r = r + y;
        } else {
            q = q + one;
            r = r - y;
        }
    }
    (q, r)
}

/**
 * Max Weighted Floor of Linear の計算 (l < r, 0 < m)
 * mwf(n, m, a, b, c, d) = max_{l <= x < r} (a*x + b*floor((c*x+d)/m))
 */
fn mwf<T>(l: T, r: T, mut m: T, mut a: T, mut b: T, mut c: T, mut d: T) -> T
where
    T: Copy
        + Ord
        + std::ops::Add<Output = T>
        + std::ops::Sub<Output = T>
        + std::ops::Mul<Output = T>
        + std::ops::Div<Output = T>
        + std::ops::Rem<Output = T>
        + std::ops::AddAssign
        + From<i8>,
{
    let zero = T::from(0);
    let one = T::from(1);
    assert!(l < r && zero < m);
    let mut n = r - l;
    let q;
    (q, c) = divrem_euclid(c, m);
    a += b * q;
    let q;
    (q, d) = divrem_euclid(l * c + d, m);
    let mut sum_acc = a * l + b * q;
    let mut max_acc = sum_acc;
    loop {
        debug_assert!(zero <= c && c < m && zero <= d && d < m);
        let n1 = n - one;
        let y_max = (c * n1 + d) / m;
        max_acc = max_acc.max(sum_acc).max(sum_acc + a * n1 + b * y_max);
        if (a <= zero && b <= zero) || (a >= zero && b >= zero) || y_max == zero {
            return max_acc;
        }
        if a < zero {
            sum_acc += a + b;
        }
        n = y_max;
        d = m - d - one;
        std::mem::swap(&mut a, &mut b);
        std::mem::swap(&mut c, &mut m);
        debug_assert!(zero < n && zero < m && zero <= c && zero <= d);
        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