結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー akakimidori
提出日時 2025-12-04 08:08:45
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 192 ms / 2,000 ms
コード長 9,493 bytes
記録
コンパイル時間 12,816 ms
コンパイル使用メモリ 399,960 KB
実行使用メモリ 14,144 KB
最終ジャッジ日時 2025-12-04 08:09:04
合計ジャッジ時間 18,370 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: type alias `Map` is never used
 --> src/main.rs:4:6
  |
4 | type Map<K, V> = BTreeMap<K, V>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: type alias `Set` is never used
 --> src/main.rs:5:6
  |
5 | type Set<T> = BTreeSet<T>;
  |      ^^^

warning: type alias `Deque` is never used
 --> src/main.rs:6:6
  |
6 | type Deque<T> = VecDeque<T>;
  |      ^^^^^

warning: associated items `dx`, `dy`, and `flush` are never used
   --> src/main.rs:113:8
    |
109 | / impl<T, const A: usize, const B: usize, const OP: bool> GenericFloorSum<T, A, B, OP>
110 | | where
111 | |     T: SemiRing + Copy,
    | |_______________________- associated items in this implementation
112 |   {
113 |       fn dx() -> Self {
    |          ^^
...
119 |       fn dy() -> Self {
    |          ^^
...
124 |       fn flush(&self) -> [[T; B]; A] {
    |          ^^^^^

warning: function `floor_flush_matrix` is never used
   --> src/main.rs:147:4
    |
147 | fn floor_flush_matrix<T, const N: usize>() -> [[T; N]; N]
    |    ^^^^^^^^^^^^^^^^^^

ソースコード

diff #
raw source code 

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn run() {
    input! {
        t: usize,
        ask: [(usize, usize, i64, i64, usize, usize); t],
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for (n, m, a, b, c, d) in ask {
        let dx = D::new(a, 0);
        let dy = D::new(b, std::i64::MIN / 2);
        let ans = floor_monoid(n, m, c, d, dx, dy).max;
        writeln!(out, "{}", ans).ok();
    }
}

#[derive(Clone)]
struct D {
    sum: i64,
    max: i64,
}

impl D {
    fn new(sum: i64, max: i64) -> Self {
        D {sum, max }
    }
}

impl Monoid for D {
    fn id() -> D {
        Self::new(0, std::i64::MIN / 2)
    }
    fn merge(&self, rhs: &Self) -> Self {
        Self::new(self.sum + rhs.sum, self.max.max(rhs.max + self.sum))
    }
}

fn main() {
    run();
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
// OP=false の時、モノイドではなくなるのに注意
// 基本的に自作のdx dy を使うとかじゃない限りはそのままでいいはず
#[derive(Clone)]
pub struct GenericFloorSum<T, const A: usize, const B: usize, const OP: bool = false> {
    x: [T; A],
    y: [T; B],
    s: [[T; B]; A],
}

impl<T, const A: usize, const B: usize, const OP: bool> GenericFloorSum<T, A, B, OP>
where
    T: SemiRing + Copy,
{
    fn dx() -> Self {
        let mut res = Self::id();
        res.x[1] = T::one();
        res.s[0][0] = T::one();
        res
    }
    fn dy() -> Self {
        let mut res = Self::id();
        res.y[1] = T::one();
        res
    }
    fn flush(&self) -> [[T; B]; A] {
        let mat = floor_flush_matrix::<T, A>();
        let mut ns = [[T::zero(); B]; A];
        for (ns, mat) in ns.iter_mut().zip(mat.iter()) {
            for (s, m) in self.s.iter().zip(mat.iter()) {
                for (ns, s) in ns.iter_mut().zip(s.iter()) {
                    *ns = *ns + *m * *s;
                }
            }
        }
        let mat = floor_flush_matrix::<T, B>();
        let mut s = [[T::zero(); B]; A];
        for (s, ns) in s.iter_mut().zip(ns.iter()) {
            for (s, mat) in s.iter_mut().zip(mat.iter()) {
                for (m, ns) in mat.iter().zip(ns.iter()) {
                    *s = *s + *m * *ns;
                }
            }
        }
        s
    }
}

fn floor_flush_matrix<T, const N: usize>() -> [[T; N]; N]
where
    T: SemiRing + Copy,
{
    let mut res = [[T::zero(); N]; N];
    let mut dp = [T::zero(); N];
    dp[0] = T::one();
    res[0] = dp;
    for i in 1..N {
        let mut next = [T::zero(); N];
        let mut mul = T::one();
        for j in 1..N {
            next[j] = mul * (dp[j - 1] + dp[j]);
            mul = mul + T::one();
        }
        dp = next;
        res[i] = dp;
    }
    res
}

impl<T, const A: usize, const B: usize, const OP: bool> Monoid for GenericFloorSum<T, A, B, OP>
where
    T: SemiRing + Copy,
{
    fn id() -> Self {
        let mut res = Self {
            x: [T::zero(); A],
            y: [T::zero(); B],
            s: [[T::zero(); B]; A],
        };
        res.x[0] = T::one();
        res.y[0] = T::one();
        res
    }
    fn merge(&self, rhs: &Self) -> Self {
        if OP {
            let mut x = [T::zero(); A];
            let mut ns = [[T::zero(); B]; A];
            for (i, a) in self.x.iter().enumerate() {
                for (c, b) in x[i..].iter_mut().zip(rhs.x.iter()) {
                    *c = *c + *a * *b;
                }
                for (ns, b) in ns[i..].iter_mut().zip(rhs.s.iter()) {
                    for (ns, b) in ns.iter_mut().zip(b.iter()) {
                        *ns = *ns + *a * *b;
                    }
                }
            }
            let mut y = [T::zero(); B];
            let mut s = self.s;
            for (i, a) in self.y.iter().enumerate() {
                for (c, b) in y[i..].iter_mut().zip(rhs.y.iter()) {
                    *c = *c + *a * *b;
                }
                for (s, ns) in s.iter_mut().zip(ns.iter()) {
                    for (c, b) in s[i..].iter_mut().zip(ns.iter()) {
                        *c = *c + *a * *b;
                    }
                }
            }
            Self { x, y, s }
        } else {
            let mut x = rhs.x;
            let mut ns = rhs.s;
            for i in 1..A {
                let a = self.x[i];
                for j in i..A {
                    x[j] = x[j] + a * rhs.x[j - i];
                }
                for j in i..A {
                    for k in 0..B {
                        ns[j][k] = ns[j][k] + a * rhs.s[j - i][k];
                    }
                }
            }
            let mut y = rhs.y;
            let mut s = ns;
            for i in 1..B {
                let a = self.y[i];
                for j in i..B {
                    y[j] = y[j] + a * rhs.y[j - i];
                }
                for k in 0..A {
                    for j in i..B {
                        s[k][j] = s[k][j] + a * ns[k][j - i];
                    }
                }
            }
            for i in 0..A {
                for j in 0..B {
                    s[i][j] = s[i][j] + self.s[i][j];
                }
            }
            Self { x, y, s }
        }
    }
}

pub trait Monoid: Clone {
    fn id() -> Self;
    fn merge(&self, rhs: &Self) -> Self;
    fn pow(&self, mut n: usize) -> Self {
        if n == 0 {
            return Self::id();
        }
        if n == 1 {
            return self.clone();
        }
        let mut t = self.clone();
        n -= 1;
        let mut r = self.clone();
        while n > 1 {
            if n & 1 == 1 {
                t = t.merge(&r);
            }
            r = r.merge(&r);
            n >>= 1;
        }
        t.merge(&r)
    }
}

pub fn floor_monoid<T>(
    mut n: usize,
    mut m: usize,
    mut a: usize,
    mut b: usize,
    mut x: T,
    mut y: T,
) -> T
where
    T: Monoid,
{
    let mut front = T::id();
    let mut tail = T::id();
    let mut c = (a * n + b) / m;
    loop {
        if a >= m {
            let q = a / m;
            a %= m;
            x = x.merge(&y.pow(q));
            c -= q * n;
        }
        if b >= m {
            let q = b / m;
            b %= m;
            front = front.merge(&y.pow(q));
            c -= q;
        }
        if c == 0 {
            break;
        }
        let need = (m * c - b + a - 1) / a;
        tail = y.merge(&x.pow(n - need)).merge(&tail);
        n = c - 1;
        c = need;
        b = m - b + a - 1;
        std::mem::swap(&mut a, &mut m);
        std::mem::swap(&mut x, &mut y);
    }
    front.merge(&x.pow(n)).merge(&tail)
}
// ---------- begin trait ----------

use std::ops::*;

pub trait Zero: Sized + Add<Self, Output = Self> {
    fn zero() -> Self;
    fn is_zero(&self) -> bool;
}

pub trait One: Sized + Mul<Self, Output = Self> {
    fn one() -> Self;
    fn is_one(&self) -> bool;
}

pub trait Group: Zero + Sub<Output = Self> + Neg<Output = Self> {}
pub trait SemiRing: Zero + One {}
pub trait Ring: SemiRing + Group {}
pub trait Field: Ring + Div<Output = Self> {}

impl<T> Group for T where T: Zero + Sub<Output = Self> + Neg<Output = Self> {}
impl<T> SemiRing for T where T: Zero + One {}
impl<T> Ring for T where T: SemiRing + Group {}
impl<T> Field for T where T: Ring + Div<Output = Self> {}

pub fn zero<T: Zero>() -> T {
    T::zero()
}

pub fn one<T: One>() -> T {
    T::one()
}

pub fn pow<T: One + Clone>(mut r: T, mut n: usize) -> T {
    let mut t = one();
    while n > 0 {
        if n & 1 == 1 {
            t = t * r.clone();
        }
        r = r.clone() * r;
        n >>= 1;
    }
    t
}

pub fn pow_sum<T: SemiRing + Clone>(mut r: T, mut n: usize) -> T {
    let mut ans = T::zero();
    let mut sum = T::one();
    while n > 0 {
        if n & 1 == 1 {
            ans = ans * r.clone() + sum.clone();
        }
        sum = sum * (T::one() + r.clone());
        r = r.clone() * r;
        n >>= 1;
    }
    ans
}
// ---------- end trait ----------
0