結果
| 問題 |
No.3129 Multiple of Twin Subarray
|
| コンテスト | |
| ユーザー |
 White-Green
|
| 提出日時 | 2025-04-25 22:58:51 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,922 bytes |
| コンパイル時間 | 13,685 ms |
| コンパイル使用メモリ | 403,480 KB |
| 実行使用メモリ | 15,972 KB |
| 最終ジャッジ日時 | 2025-04-25 22:59:20 |
| 合計ジャッジ時間 | 16,616 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 WA * 15 RE * 1 |
コンパイルメッセージ
warning: unnecessary parentheses around assigned value --> src/main.rs:30:36 | 30 | let (max1, max_range1, max2) = (max_range_sum(&a_sums)); | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 30 - let (max1, max_range1, max2) = (max_range_sum(&a_sums)); 30 + let (max1, max_range1, max2) = max_range_sum(&a_sums); | warning: unnecessary parentheses around assigned value --> src/main.rs:32:36 | 32 | let (min1, min_range1, min2) = (max_range_sum(&a_sums)); | ^ ^ | help: remove these parentheses | 32 - let (min1, min_range1, min2) = (max_range_sum(&a_sums)); 32 + let (min1, min_range1, min2) = max_range_sum(&a_sums); | warning: unnecessary parentheses around block return value --> src/main.rs:40:9 | 40 | ((a_sums[max_range1.end] - a_sums[m]) * (a_sums[m] - a_sums[max_range1.start])) | ^ ^ | help: remove these parentheses | 40 - ((a_sums[max_range1.end] - a_sums[m]) * (a_sums[m] - a_sums[max_range1.start])) 40 + (a_sums[max_range1.end] - a_sums[m]) * (a_sums[m] - a_sums[max_range1.start]) | warning: unnecessary parentheses around block return value --> src/main.rs:43:9 | 43 | ((a_sums[min_range1.end] - a_sums[m]) * (a_sums[m] - a_sums[min_range1.start])) | ^ ^ | help: remove these parentheses | 43 - ((a_sums[min_range1.end] - a_sums[m]) * (a_sums[m] - a_sums[min_range1.start])) 43 + (a_sums[min_range1.end] - a_sums[m]) * (a_sums[m] - a_sums[min_range1.start]) | warning: value assigned to `current_sum` is never read --> src/main.rs:55:13 | 55 | let mut current_sum = 0; | ^^^^^^^^^^^ | = h
ソースコード
#![allow(unused_imports)]
#![allow(dead_code)]
use std::cell::RefCell;
use std::cmp::{Ordering, Reverse};
use std::collections::btree_map::Entry as BTreeMapEntry;
use std::collections::hash_map::{Entry as HashMapEntry, Entry};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt::{Debug, Display, Formatter, Write};
use std::hash::Hash;
use std::io::{stdin, BufRead, BufWriter, Write as _};
use std::ops::{Bound, ControlFlow, Range, RangeBounds, RangeInclusive};
use std::rc::Rc;
use std::str::FromStr;
use std::sync::atomic;
use std::sync::atomic::AtomicUsize;
use std::thread::LocalKey;
use std::time::{Duration, Instant};
use std::{array, convert, io, iter, mem, ptr};
pub fn solve(InputObject { cin }: InputObject) {
let n = cin.next();
let a: Vec<i64> = cin.next_vec(n);
let mut a_sums = iter::once(0)
.chain(a.into_iter().scan(0, |acc, x| {
*acc += x;
Some(*acc)
}))
.collect::<Vec<_>>();
let (max1, max_range1, max2) = (max_range_sum(&a_sums));
a_sums.iter_mut().for_each(|x| *x = -*x);
let (min1, min_range1, min2) = (max_range_sum(&a_sums));
let ans = ([
max2.map(|(max2, _)| max1 * max2),
min2.map(|(min2, _)| min1 * min2)
])
.into_iter()
.flatten()
.chain((max_range1.start + 1..max_range1.end).map(|m| {
((a_sums[max_range1.end] - a_sums[m]) * (a_sums[m] - a_sums[max_range1.start]))
}))
.chain((min_range1.start + 1..min_range1.end).map(|m| {
((a_sums[min_range1.end] - a_sums[m]) * (a_sums[m] - a_sums[min_range1.start]))
}))
.max()
.unwrap();
println!("{}", ans);
}
fn max_range_sum(a_sums: &[i64]) -> (i64, Range<usize>, Option<(i64, Range<usize>)>) {
let mut max2 = None::<(i64, Range<usize>)>;
let mut max_range1 = 0..0;
let mut max1 = i64::MIN;
let mut left = 0;
let mut current_sum = 0;
for right in 1..a_sums.len() {
current_sum = a_sums[right] - a_sums[left];
if current_sum <= 0 {
if left < right - 1 {
if match max2 {
None => true,
Some((max2, _)) => max1 > max2,
} {
max2 = Some((max1, max_range1));
}
} else {
if match max2 {
None => true,
Some((max2, _)) => current_sum > max2,
} {
max2 = Some((current_sum, left..right));
}
}
max_range1 = 0..0;
max1 = i64::MIN;
left = right;
continue;
}
if current_sum > max1 {
max1 = current_sum;
max_range1 = left..right;
}
}
if max1 == i64::MIN {
let (max, range) = max2.unwrap();
return (max, range, None);
}
(max1, max_range1, max2)
}
pub struct InputObject<'a> {
cin: &'a mut ConsoleInput,
}
fn input(cin: &mut ConsoleInput) -> InputObject {
InputObject { cin }
}
pub fn main() {
let mut cin = ConsoleInput::new();
let input = input(&mut cin);
solve(input);
}
// libraries below
pub struct ConsoleInput {
queue: VecDeque<String>,
}
pub trait Input {
fn next<T: FromStr>(&mut self) -> T;
fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.next()).collect()
}
}
pub trait Output {
fn write(&self);
}
impl Output for () {
fn write(&self) {}
}
impl Input for ConsoleInput {
fn next<T: FromStr>(&mut self) -> T {
match self.read().parse() {
Ok(value) => value,
_ => panic!("parse error"),
}
}
}
impl ConsoleInput {
fn new() -> Self {
Self {
queue: VecDeque::new(),
}
}
fn read(&mut self) -> String {
loop {
if let Some(s) = self.queue.pop_front() {
return s;
}
let mut s = String::new();
stdin().read_line(&mut s).expect("failed to read");
for s in s.split_ascii_whitespace() {
self.queue.push_back(String::from(s));
}
}
}
}
fn binary_search(range: Range<usize>, f: impl Fn(usize) -> Ordering) -> Result<usize, usize> {
let mut start = range.start;
let mut len = range.len();
if len == 0 {
return Err(0);
}
while len > 1 {
let half = len / 2;
let mid = start + half;
if f(mid) != Ordering::Greater {
start = mid;
}
len -= half;
}
match f(start) {
Ordering::Equal => Ok(start),
Ordering::Less => Err(start + 1),
Ordering::Greater => Err(start),
}
}
fn all_bits() -> impl Iterator<Item = impl Iterator<Item = (usize, bool)>> {
(0usize..).map(|i| (0usize..).map(move |j| (j, (i >> j) & 1 != 0)))
}
#[cfg(test)]
mod tests;