// 問題文と制約は読みましたか? // #[fastout] fn main() { input! { r :i64, // 岩井星人の初期レート p :i64, // 合成のコスト q :i64, // 色変換のコスト a: i64, b: i64, c: i64, d: i64, } let sum: i64 = [a, b, c, d].iter().copied().sum(); let ans = bin_search(0, sum / 3 + 1, |x| { // x 人作る let cost1 = x * p; // 合成 let cost2: i64 = [a, b, c] .map(|k| { let lack = (x - k).max(0); lack * q }) .iter() .sum(); // 変換 cost1 + cost2 <= r }); println!("{}", ans) } // ====== import ====== #[allow(unused_imports)] use { itertools::{Itertools, chain, iproduct, izip}, proconio::{ derive_readable, fastout, input, marker::{Bytes, Chars, Usize1}, }, std::{ cmp::Reverse, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet}, }, }; // ====== output func ====== #[allow(unused_imports)] use print_util::*; pub mod print_util { use itertools::Itertools; use proconio::fastout; #[fastout] pub fn print_vec(arr: &[T]) { for a in arr { println!("{}", a); } } #[fastout] pub fn print_vec_1line(arr: &[T]) { println!("{}", arr.iter().join(" ")); } #[fastout] pub fn print_vec2>(arr: &[R]) { for row in arr { println!("{}", row.as_ref().iter().join(" ")); } } pub fn print_bytes(bytes: &[u8]) { println!("{}", std::str::from_utf8(bytes).unwrap()); } pub fn print_chars(chars: &[char]) { println!("{}", chars.iter().collect::()); } #[fastout] pub fn print_vec_bytes>(vec_bytes: &[R]) { for row in vec_bytes { println!("{}", std::str::from_utf8(row.as_ref()).unwrap()); } } #[fastout] pub fn print_vec_chars>(vec_chars: &[R]) { for row in vec_chars { println!("{}", row.as_ref().iter().collect::()); } } pub fn print_yesno(ans: bool) { println!("{}", if ans { "Yes" } else { "No" }); } } // ====== snippet ====== /// 二分探索をする。 /// ```text /// ng ng ng ok ok ok /// ↑ここの引数の値を返す /// ``` /// # 計算量 /// O(log(|ok - ng|)) /// ## Arguments /// * ok != ng /// * |ok - ng| <= 2^63 - 1, |ok + ng| <= 2^63 - 1 /// * p の定義域について /// * ng < ok の場合、p は区間 ng..ok で定義されている。 /// * ok < ng の場合、p は区間 ok..ng で定義されている。 /// * p の単調性について /// * ng < ok の場合、p は単調増加 /// * ok < ng の場合、p は単調減少 /// ## Return /// * ng < ok の場合: I = { i in ng..ok | p(i) == true } としたとき /// * I が空でなければ、min I を返す。 /// * I が空ならば、ok を返す。 /// * ok < ng の場合: I = { i in ok..ng | p(i) == true } としたとき /// * I が空でなければ、max I を返す。 /// * I が空ならば、ok を返す。 pub fn bin_search(mut ok: i64, mut ng: i64, mut p: F) -> i64 where F: FnMut(i64) -> bool, { debug_assert!(ok != ng); debug_assert!(ok.checked_sub(ng).is_some()); debug_assert!(ok.checked_add(ng).is_some()); while num::abs(ok - ng) > 1 { let mid = (ok + ng) / 2; debug_assert!(mid != ok); debug_assert!(mid != ng); if p(mid) { ok = mid; } else { ng = mid; } } ok }