Submission #1960234
Source Code Expand
use std::io; use std::cmp; // read a line(without line feed) fn read_line() -> String { let mut in_str = String::new(); io::stdin().read_line(&mut in_str).unwrap(); return in_str.trim().to_string(); } // read wods on a line pub fn read_words_in_line() -> Vec<String> { let s = read_line(); return s.split_whitespace().map(|x| x.to_string()).collect::<Vec<String>>() } // read type t on a line pub fn read_t_in_line<T : std::str::FromStr>() -> Vec<T> { let mut v : Vec<T> = Vec::new(); for e in read_words_in_line().iter().map(|x| x.parse::<T>()) { if let Ok(r) = e { v.push(r); } else{ return Vec::new(); } } return v; } // sort slice pub fn sort<T : std::cmp::Ord>(slice : &mut [T]) { slice.sort(); } // sort slice by reverse order pub fn sort_rev<T : std::cmp::Ord>(slice : &mut [T]) { slice.sort_by(|x, y| y.cmp(x)); } pub fn min<T : std::cmp::Ord>(a : T, b : T) -> T{ return cmp::min(a, b); } pub fn max<T : std::cmp::Ord>(a : T, b : T) -> T{ return cmp::max(a, b); } fn main(){ const MAX_N : usize = 100010; let v = read_t_in_line::<i32>(); let(n, h) = (v[0] as usize, v[1]); let mut aa = [0 ; MAX_N]; let mut bb = [0 ; MAX_N]; for i in 0..n { let v2 = read_t_in_line::<i32>(); let (a, b) = (v2[0], v2[1]); aa[i] = a; bb[i] = b; } // aaとbbをそれぞれsort // bbを大きい順番に使う, aaは一番大きい値しか利用しない let a_slice : &mut [i32] = &mut aa[0..n]; sort_rev(a_slice); let b_slice : &mut [i32] = &mut bb[0..n]; sort_rev(b_slice); let a_max = a_slice[0]; let mut min_count = (h + a_max - 1) / a_max; let mut b_sum = 0; for i in 0..b_slice.len() { b_sum += b_slice[i]; if b_sum >= h { min_count = min(min_count, i as i32 + 1); break; } else{ min_count = min(min_count, ((h - b_sum) + a_max - 1) / a_max + i as i32 + 1); } } println!("{}", min_count); }
Submission Info
Submission Time | |
---|---|
Task | D - Katana Thrower |
User | ishikado |
Language | Rust (1.15.1) |
Score | 400 |
Code Size | 2187 Byte |
Status | AC |
Exec Time | 52 ms |
Memory | 5116 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03, a04 |
All | a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 2 ms | 5116 KB |
a02 | AC | 2 ms | 5116 KB |
a03 | AC | 2 ms | 5116 KB |
a04 | AC | 2 ms | 5116 KB |
b05 | AC | 2 ms | 5116 KB |
b06 | AC | 49 ms | 5116 KB |
b07 | AC | 2 ms | 5116 KB |
b08 | AC | 49 ms | 5116 KB |
b09 | AC | 2 ms | 5116 KB |
b10 | AC | 2 ms | 5116 KB |
b11 | AC | 2 ms | 5116 KB |
b12 | AC | 2 ms | 5116 KB |
b13 | AC | 35 ms | 5116 KB |
b14 | AC | 35 ms | 5116 KB |
b15 | AC | 36 ms | 5116 KB |
b16 | AC | 35 ms | 5116 KB |
b17 | AC | 52 ms | 5116 KB |
b18 | AC | 51 ms | 5116 KB |
b19 | AC | 48 ms | 5116 KB |
b20 | AC | 50 ms | 5116 KB |
b21 | AC | 51 ms | 5116 KB |
b22 | AC | 52 ms | 5116 KB |
b23 | AC | 2 ms | 5116 KB |
b24 | AC | 3 ms | 5116 KB |