結果
問題 | No.914 Omiyage |
ユーザー |
![]() |
提出日時 | 2019-10-25 21:33:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 2,844 bytes |
コンパイル時間 | 21,538 ms |
コンパイル使用メモリ | 400,088 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-24 16:25:26 |
合計ジャッジ時間 | 14,885 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
コンパイルメッセージ
warning: unused variable: `i` --> src/main.rs:23:9 | 23 | for i in 0..n { | ^ help: if this is intentional, prefix it with an underscore: `_i` | = note: `#[warn(unused_variables)]` on by default
ソースコード
#![allow(unused_imports)]#![allow(non_snake_case)]use std::cmp::*;use std::collections::*;use std::io::Write;#[allow(unused_macros)]macro_rules! debug {($($e:expr),*) => {#[cfg(debug_assertions)]$({let (e, mut err) = (stringify!($e), std::io::stderr());writeln!(err, "{} = {:?}", e, $e).unwrap()})*};}fn main() {let v = read_vec::<usize>();let (n, m, k) = (v[0], v[1], v[2] as i64);let mut a = vec![];for i in 0..n {let v = read_vec::<i64>();a.push(v);}let mut cand1 = vec![];for i in 0..(m as i64).pow(n as u32 / 2) {let mut cand = 0;let mut i = i;for j in 0..(n / 2) {cand += a[j][i as usize % m];i /= m as i64;}cand1.push(cand);}let mut cand2 = vec![];for i in 0..(m as i64).pow(n as u32 - n as u32 / 2) {let mut cand = 0;let mut i = i;for j in n / 2..n {cand += a[j][i as usize % m];i /= m as i64;}cand2.push(cand);}cand2.sort();let mut ans = std::i64::MAX;for &c in cand1.iter() {let idx = cand2.upper_bound(&(k - c));if idx > 0 {ans = min(ans, k - c - cand2[idx - 1]);}}// debug!(cand1);// debug!(cand2);if ans == std::i64::MAX {println!("-1");return;}println!("{}", ans);}pub trait BinarySearch<T> {fn lower_bound(&self, x: &T) -> usize;fn upper_bound(&self, x: &T) -> usize;}impl<T: Ord> BinarySearch<T> for [T] {fn lower_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less => {low = mid + 1;}Ordering::Equal | Ordering::Greater => {high = mid;}}}low}fn upper_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less | Ordering::Equal => {low = mid + 1;}Ordering::Greater => {high = mid;}}}low}}fn read<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}fn read_vec<T: std::str::FromStr>() -> Vec<T> {read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()}