結果
| 問題 |
No.3293 Golden Cross
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 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 |
ソースコード
// 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}");
}