結果

問題 No.3293 Golden Cross
ユーザー koba-e964
提出日時 2025-10-03 12:55:26
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 4,080 bytes
コンパイル時間 11,301 ms
コンパイル使用メモリ 401,584 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-03 13:08:03
合計ジャッジ時間 14,514 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes.by_ref().map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr,) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}

// max (a+x+y)*(b+x+z) where dx+ey+fz <= k
// x,y,z >= 0
fn g(
    a: i64, b: i64,
    d: i64, e: i64, f: i64,
    k: i64,
) -> i64 {
    if d <= e && d <= f {
        let x = k / d;
        return (a + x) * (b + x);
    }
    // max (a+x)(b-cx) where 0 <= x <= t
    fn quad(a: i64, b: i64, c: i64, t: i64) -> i64 {
        // max -cx^2 + (b - ac)x + ab
        let u = 0.max(b - a * c) / (2 * c);
        let mut ans = a * b;
        ans = ans.max((a + t) * (b - c * t));
        for i in u..=u + 1 {
            if i <= t {
                ans = ans.max((a + i) * (b - c * i));
            }
        }
        ans
    }
    // max (a+x+y)(b+x) where dx+ey <= k
    fn g_single(
        a: i64, b: i64,
        d: i64, e: i64,
        k: i64,
    ) -> i64 {
        assert!(d % e == 0);
        let d = d / e;
        let k = k / e;
        // max (b + x)(a + k - (d - 1)x)
        quad(b, a + k, d - 1, k / d)
    }
    // max (a+y)(b+z) where ey+fz <= k
    fn g_bc(
        a: i64, b: i64,
        e: i64, f: i64,
        k: i64,
    ) -> i64 {
        if e > f {
            return g_bc(b, a, f, e, k);
        }
        assert!(f % e == 0);
        let f = f / e;
        let k = k / e;
        // max (a + k - fz)(b + z)
        quad(b, a + k, f, k / f)
    }
    if d <= f {
        return g_single(a, b, d, e, k);
    }
    if d <= e {
        return g_single(b, a, d, f, k);
    }
    assert!(d >= e + f, "d = {}, e = {}, f = {}", d, e, f);
    g_bc(a, b, e, f, k)
}

fn main() {
    input! {
        h: usize, w: usize, k: i64,
        a: [[i64; w]; h],
        b: [[i64; w]; h],
    }
    let mut row = vec![0; h];
    let mut col = vec![0; w];
    const INF: i64 = 1 << 50;
    let mut row_mi = vec![[INF; 2]; h];
    let mut col_mi = vec![[INF; 2]; w];
    for i in 0..h {
        for j in 0..w {
            row[i] += a[i][j];
            col[j] += a[i][j];
            for x in 0..2 {
                if row_mi[i][x] > b[i][j] {
                    for y in (x + 1..2).rev() {
                        row_mi[i][y] = row_mi[i][y - 1];
                    }
                    row_mi[i][x] = b[i][j];
                    break;
                }
            }
            for x in 0..2 {
                if col_mi[j][x] > b[i][j] {
                    for y in (x + 1..2).rev() {
                        col_mi[j][y] = col_mi[j][y - 1];
                    }
                    col_mi[j][x] = b[i][j];
                    break;
                }
            }
        }
    }
    let mut ans = 0;
    for i in 0..h {
        for j in 0..w {
            let row_rest_mi = if a[i][j] == row_mi[i][0] {
                row_mi[i][1]
            } else {
                row_mi[i][0]
            };
            let col_rest_mi = if a[i][j] == col_mi[j][0] {
                col_mi[j][1]
            } else {
                col_mi[j][0]
            };
            ans = ans.max(g(
                row[i], col[j],
                1 << b[i][j], 1 << row_rest_mi, 1 << col_rest_mi,
                k,
            ));
        }
    }
    println!("{ans}");
}
0