Submission #1183580
Source Code Expand
fn main() { let mut sc = cin(); let mut binom = [[0; 60]; 60]; for i in 0..60 { for j in 0..60 { binom[i][j] = if j == 0 { 1 } else if i < j { 0 } else { binom[i-1][j-1] + binom[i-1][j] } } } while sc.read() { let n = sc.next(); let a: usize = sc.next(); let b: usize = sc.next(); let mut v = sc.vec::<i64>(n); v.sort(); v.reverse(); let mut max_ave: f64 = 0.0; for k in a..b+1 { let sum: i64 = v.iter().take(k).sum(); let ave = sum as f64 / k as f64; if max_ave < ave { max_ave = ave; } } println!("{:.10}", max_ave); let mut cnt: Vec<(usize, _)> = vec![]; for &x in v.iter() { if cnt.len() == 0 || cnt.last().unwrap().1 != x { cnt.push((1, x)); } else { cnt.last_mut().unwrap().0 += 1; } } let mut ans = 0u64; for k in a..b+1 { let sum: i64 = v.iter().take(k).sum(); let ave = sum as f64 / k as f64; if ave != max_ave { continue; } let mut cur = 0; let mut x = 1u64; for &(a, _) in cnt.iter() { if cur <= k && k <= cur + a { x *= binom[a][k - cur]; // println!("binom {} {}", a, k-cur); } cur += a; } ans += x; } println!("{}", ans); } } #[allow(dead_code)] fn cin() -> Scanner<std::io::Stdin> { Scanner::new(std::io::stdin()) } #[allow(dead_code)] pub struct Scanner<T> { buf: Vec<u8>, len: usize, idx: usize, next: Option<String>, reader: T, } #[allow(dead_code)] impl<Reader: std::io::Read> Scanner<Reader> { fn new(r: Reader) -> Scanner<Reader> { Scanner { buf: vec![0; 8192], len: 0, idx: 0, next: None, reader: r, } } fn next<T: std::str::FromStr>(&mut self) -> T { self.wrapped::<T>().unwrap() } fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.next()).collect() } fn mat<T: std::str::FromStr>(&mut self, r: usize, c: usize) -> Vec<Vec<T>> { (0..r).map(|_| self.vec(c)).collect() } fn vec_char(&mut self) -> Vec<char> { self.read(); self.next.take().unwrap().chars().collect() } fn mat_char(&mut self, r: usize) -> Vec<Vec<char>> { (0..r).map(|_| self.vec_char()).collect() } fn wrapped<T: std::str::FromStr>(&mut self) -> Option<T> { self.read(); self.next.take().and_then(|s| s.parse::<T>().ok()) } fn read(&mut self) -> bool { if self.next.is_some() { return true; } let mut s = String::with_capacity(16); while let Some(c) = self.get_char() { if !c.is_whitespace() { s.push(c); } else if !s.is_empty() { break; } } self.next = if !s.is_empty() { Some(s) } else { None }; self.next.is_some() } fn get_char(&mut self) -> Option<char> { if self.idx == self.len { match self.reader.read(&mut self.buf[..]) { Ok(l) if l > 0 => { self.idx = 0; self.len = l; } _ => return None, } } self.idx += 1; Some(self.buf[self.idx - 1] as char) } }
Submission Info
Submission Time | |
---|---|
Task | D - Maximum Average Sets |
User | tubo28 |
Language | Rust (1.15.1) |
Score | 0 |
Code Size | 3871 Byte |
Status | WA |
Exec Time | 2 ms |
Memory | 4352 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 2 ms | 4352 KB |
sample_02.txt | AC | 2 ms | 4352 KB |
sample_03.txt | AC | 2 ms | 4352 KB |
sample_04.txt | AC | 2 ms | 4352 KB |
subtask_1_1.txt | AC | 2 ms | 4352 KB |
subtask_1_10.txt | AC | 2 ms | 4352 KB |
subtask_1_11.txt | WA | 2 ms | 4352 KB |
subtask_1_12.txt | AC | 2 ms | 4352 KB |
subtask_1_13.txt | AC | 2 ms | 4352 KB |
subtask_1_14.txt | AC | 2 ms | 4352 KB |
subtask_1_15.txt | AC | 2 ms | 4352 KB |
subtask_1_2.txt | AC | 2 ms | 4352 KB |
subtask_1_3.txt | AC | 2 ms | 4352 KB |
subtask_1_4.txt | AC | 2 ms | 4352 KB |
subtask_1_5.txt | AC | 2 ms | 4352 KB |
subtask_1_6.txt | AC | 2 ms | 4352 KB |
subtask_1_7.txt | AC | 2 ms | 4352 KB |
subtask_1_8.txt | AC | 2 ms | 4352 KB |
subtask_1_9.txt | AC | 2 ms | 4352 KB |