結果
問題 |
No.3129 Multiple of Twin Subarray
|
ユーザー |
|
提出日時 | 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;