#![allow(non_snake_case)] pub use __cargo_equip::prelude::*; use proconio::{fastout, input}; use wavelet_matrix::WaveletMatrix; #[fastout] fn main() { input! { N: usize, A: [i64; N], } let sorted_a = { let mut a = A.clone(); a.sort_unstable(); a.dedup(); a }; let compressed = A .iter() .map(|a| sorted_a.binary_search(a).unwrap()) .collect::>(); let wm = WaveletMatrix::new(&compressed); let mut ans = 0; for k in 1..N { let all_teams = N / k; let median_id = (k + 1) / 2 - 1; let left_sum = { let mut left_sum = vec![0; all_teams + 1]; for i in 0..all_teams { // [i * k, (i + 1) * k) let left = i * k; let right = (i + 1) * k; let mid = wm.quantile(left..right, median_id); let power = sorted_a[mid] * k as i64; left_sum[i + 1] = left_sum[i] + power; } left_sum }; let right_sum = { let mut right_sum = vec![0; all_teams + 1]; for i in 0..all_teams { // [N - (i + 1) * k, N - i * k) let left = N - (i + 1) * k; let right = N - i * k; let mid = wm.quantile(left..right, median_id); let power = sorted_a[mid] * k as i64; right_sum[i + 1] = right_sum[i] + power; } right_sum }; debug!(k, all_teams, left_sum, right_sum); // 累積Max let right_cnt_max = { let mut right_cnt_max = right_sum; for i in 1..=all_teams { right_cnt_max[i] = right_cnt_max[i].max(right_cnt_max[i - 1]); } right_cnt_max }; for left_cnt in 0..=all_teams { let right_cnt = all_teams - left_cnt; // [0, right_cnt]の中での最大値 let power = left_sum[left_cnt] + right_cnt_max[right_cnt]; ans = ans.max(power); } } println!("{}", ans); } /// https://maguro.dev/debug-macro/ #[macro_export] macro_rules! debug { ($($a:expr),* $(,)*) => { #[cfg(debug_assertions)] eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*); }; } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `bitdict 0.1.0 (path+████████████████████████████████████████████████████████████)` published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__bitdict_0_1_0` /// - `internal_bits 0.1.0 (path+████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_bits_0_1_0` /// - `wavelet_matrix 0.1.0 (path+███████████████████████████████████████████████████████████████████)` published in ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git licensed under `CC0-1.0` as `crate::__cargo_equip::crates::wavelet_matrix` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod __bitdict_0_1_0 {#[derive(Debug,Clone,Copy)]struct Block{bit:u64,cum_sum_popcnt:u32,}#[derive(Debug,Clone)]pub struct BitDict{len:usize,blocks:Vec,all_popcnt:usize,one_select:Vec,zero_select:Vec,}impl From<&[bool]>for BitDict{fn from(bitvec:&[bool])->Self{let len=bitvec.len();let mut ret=Self::new(len);for(i,&b)in bitvec.iter().enumerate(){if b{ret.set(i);}}ret.build();ret}}impl BitDict{pub fn new(len:usize)->Self{Self{len,blocks:vec![Block{bit:0,cum_sum_popcnt:0};(len>>6)+1],all_popcnt:0,one_select:Vec::new(),zero_select:Vec::new(),}}pub fn rank1_all(&self)->usize{self.all_popcnt}pub fn rank0_all(&self)->usize{self.len-self.all_popcnt}pub fn access(&self,i:usize)->bool{debug_assert!(i>6].bit>>(i&63))&1==1}pub fn set(&mut self,i:usize){debug_assert!(i>6].bit|=1<<(i&63);}pub fn build(&mut self){let all_popcnt=self.blocks.iter().map(|b|b.bit.count_ones()).sum::()as usize;let mut popcnt=0;let one_num=(all_popcnt>>6)+1;let zero_num=((self.len-all_popcnt)>>6)+1;let mut one_select=Vec::with_capacity(one_num);let mut zero_select=Vec::with_capacity(zero_num);for(i,b)in self.blocks.iter_mut().enumerate(){if popcnt as usize>=one_select.len()<<6{one_select.push(i as u32);}if(i<<6)-popcnt as usize>=zero_select.len()<<6{zero_select.push(i as u32);}b.cum_sum_popcnt=popcnt;popcnt+=b.bit.count_ones();}assert_eq!(popcnt as usize,all_popcnt);self.all_popcnt=all_popcnt;self.one_select=one_select;self.zero_select=zero_select;}pub fn rank_1(&self,i:usize)->usize{debug_assert!(i<=self.len);let Block{bit:block,cum_sum_popcnt,}=self.blocks[i>>6];let mask=(1<<(i&63))-1;let popcnt=(block&mask).count_ones();(cum_sum_popcnt+popcnt)as usize}pub fn rank_0(&self,i:usize)->usize{i-self.rank_1(i)}pub fn select_1(&self,i:usize)->Option{if i>=self.all_popcnt{return None;}let mut ok=if let Some(&ok)=self.one_select.get(i>>6){ok.saturating_sub(1)as usize}else{self.blocks.len().saturating_sub(1)};let mut ng=if let Some(&ng)=self.one_select.get((i>>6)+1){ng as usize}else{self.blocks.len()};let i=i as u32;while ng-ok>1{let mid=(ok+ng)>>1;if self.blocks[mid].cum_sum_popcnt<=i{ok=mid;}else{ng=mid;}}let rem=i-self.blocks[ok].cum_sum_popcnt;let offset=select1_u64(self.blocks[ok].bit,rem as usize);Some((ok<<6)+offset as usize)}pub fn select_0(&self,i:usize)->Option{let all_0=self.len-self.all_popcnt;if i>=all_0{return None;}let mut ok=if let Some(&ok)=self.zero_select.get(i>>6){ok.saturating_sub(1)as usize}else{self.blocks.len().saturating_sub(1)};let mut ng=if let Some(&ng)=self.zero_select.get((i>>6)+1){ng as usize}else{self.blocks.len()};while ng-ok>1{let mid=(ok+ng)>>1;if((mid<<6)-self.blocks[mid].cum_sum_popcnt as usize)<=i{ok=mid;}else{ng=mid;}}let rem=i-((ok<<6)-self.blocks[ok].cum_sum_popcnt as usize);let offset=select1_u64(!self.blocks[ok].bit,rem);Some((ok<<6)+offset as usize)}}#[cfg(target_arch="x86_64")]fn select1_u64(x:u64,index:usize)->u32{use std::arch::x86_64::_pdep_u64;let z=1<u32{let mut left=0;let mut right=64;while right-left>1{let mid=(left+right)>>1;if(x&((1<index as u32{right=mid;}else{left=mid;}}left}} pub mod __internal_bits_0_1_0 {pub fn ceil_log2(n:u32)->u32{32-n.saturating_sub(1).leading_zeros()}} pub mod wavelet_matrix {use crate::__cargo_equip::preludes::wavelet_matrix::*;use bitdict::BitDict;use internal_bits::ceil_log2;use std::ops::RangeBounds;#[derive(Debug,Clone)]pub struct WaveletMatrix{upper_bound:usize,len:usize,indices:Vec,sorted_positions:Vec>,counts:Vec,}impl WaveletMatrix{pub fn new(compressed_list:&[usize])->Self{let len=compressed_list.len();let upper_bound=*compressed_list.iter().max().unwrap_or(&0)+1;let log=ceil_log2(upper_bound as u32+1)as usize;let mut indices=vec![BitDict::new(len);log];let mut tmp=vec![Vec::with_capacity(len);2];let mut list=compressed_list.to_vec();for(ln,index)in indices.iter_mut().enumerate().rev(){for(i,x)in list.drain(..).enumerate(){if(x>>ln)&1==1{index.set(i);tmp[1].push(x);}else{tmp[0].push(x);}}index.build();list.append(&mut tmp[0]);list.append(&mut tmp[1]);}let mut sorted_positions=vec![None;upper_bound+1];let mut counts=vec![0;upper_bound+1];for(i,&x)in list.iter().enumerate(){if sorted_positions[x].is_none(){sorted_positions[x]=Some(i);}counts[x]+=1;}Self{upper_bound,len,indices,sorted_positions,counts,}}pub fn access(&self,mut pos:usize)->usize{assert!(posusize{if self.sorted_positions.get(num).unwrap_or(&None).is_none(){return 0;}assert!(pos<=self.len);for(ln,index)in self.indices.iter().enumerate().rev(){let bit=(num>>ln)&1;if bit==1{pos=index.rank0_all()+index.rank_1(pos);}else{pos=index.rank_0(pos);}}pos-self.sorted_positions[num].unwrap()}pub fn rank_less_eq_more>(&self,num:usize,range:R,)->(usize,usize,usize){let(mut begin,mut end)=self.get_pos_range(range);let range_len=end-begin;if num>=self.upper_bound{return(range_len,0,0);}let mut less=0;let mut more=0;for(ln,index)in self.indices.iter().enumerate().rev(){let bit=(num>>ln)&1;let rank1_begin=index.rank_1(begin);let rank1_end=index.rank_1(end);let rank0_begin=begin-rank1_begin;let rank0_end=end-rank1_end;if bit==1{less+=rank0_end-rank0_begin;begin=index.rank0_all()+rank1_begin;end=index.rank0_all()+rank1_end;}else{more+=rank1_end-rank1_begin;begin=rank0_begin;end=rank0_end;}}let eq=range_len-less-more;(less,eq,more)}pub fn select(&self,num:usize,pos:usize)->Option{if pos>=*self.counts.get(num)?{return None;}let mut ret=self.sorted_positions[num].unwrap()+pos;for(ln,index)in self.indices.iter().enumerate(){let bit=(num>>ln)&1;if bit==1{ret=index.select_1(ret-index.rank0_all()).unwrap();}else{ret=index.select_0(ret).unwrap();}}Some(ret)}fn get_pos_range>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let left=match range.start_bound(){Included(&x)=>x,Excluded(&x)=>x+1,Unbounded=>0,};let right=match range.end_bound(){Included(&x)=>x+1,Excluded(&x)=>x,Unbounded=>self.len,};assert!(left<=right&&right<=self.len);(left,right)}pub fn quantile>(&self,range:R,mut k:usize)->usize{let(mut begin,mut end)=self.get_pos_range(range);assert!(k>(&self,range:R)->(usize,usize){use std::ops::Bound::*;let left=match range.start_bound(){Included(&x)=>x,Excluded(&x)=>x+1,Unbounded=>0,}.min(self.upper_bound);let right=match range.end_bound(){Included(&x)=>x+1,Excluded(&x)=>x,Unbounded=>self.upper_bound,}.min(self.upper_bound);assert!(left<=right);(left,right)}pub fn range_freq+Clone,R2:RangeBounds>(&self,pos_range:R1,num_range:R2,)->usize{let(num_begin,num_end)=self.get_num_range(num_range);if num_begin>=num_end{return 0;}let cnt_begin=self.rank_less_eq_more(num_begin,pos_range.clone()).0;let cnt_end=self.rank_less_eq_more(num_end,pos_range).0;cnt_end-cnt_begin}pub fn next_value+Clone>(&self,range:R,lower:usize,)->Option{let(less,eq,upper)=self.rank_less_eq_more(lower,range.clone());if eq>0{return Some(lower);}if upper==0{return None;}Some(self.quantile(range,less))}pub fn prev_value+Clone>(&self,range:R,upper:usize,)->Option{let less=self.rank_less_eq_more(upper,range.clone()).0;if less==0{return None;}Some(self.quantile(range,less-1))}}} } pub(crate) mod macros { pub mod __bitdict_0_1_0 {} pub mod __internal_bits_0_1_0 {} pub mod wavelet_matrix {} } pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;} mod preludes { pub mod __bitdict_0_1_0 {} pub mod __internal_bits_0_1_0 {} pub mod wavelet_matrix {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__bitdict_0_1_0 as bitdict,__internal_bits_0_1_0 as internal_bits};} } }