結果
問題 |
No.1430 Coup de Coupon
|
ユーザー |
![]() |
提出日時 | 2021-03-14 16:35:09 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 788 ms / 2,000 ms |
コード長 | 1,847 bytes |
コンパイル時間 | 14,084 ms |
コンパイル使用メモリ | 397,752 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-06 06:20:36 |
合計ジャッジ時間 | 22,677 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
use std::collections::BTreeMap; fn main() { let ref mut buf = String::new(); std::io::Read::read_to_string(&mut std::io::stdin(), buf).ok(); let mut iter = buf.split_whitespace(); macro_rules! scan { ([$t:tt; $n:expr]) => ((0..$n).map(|_| scan!($t)).collect::<Vec<_>>()); (($($t:tt),*)) => (($(scan!($t)),*)); (Usize1) => (scan!(usize) - 1); (Bytes) => (scan!(String).into_bytes()); ($t:ty) => (iter.next().unwrap().parse::<$t>().unwrap()); } let (n, c) = scan!((usize, usize)); let mut items = scan!([i32; n]); items.sort_by(|a, b| b.cmp(a)); let mut coupons = vec![vec![]; 2]; for _ in 0..c { let (t, x) = scan!((Usize1, i32)); coupons[t].push(x); } for coupon in coupons.iter_mut() { (*coupon).sort_by(|a, b| b.cmp(a)); } let len1 = coupons[0].len(); let len2 = coupons[1].len(); let mut map = BTreeMap::new(); map.insert((0, 0), 0); let mut sum = 0; for i in 0..n { let p = items[i]; if i >= c { sum += p; continue; } for c1 in (0..=i.min(len1)).rev() { let c2 = i - c1; if c2 > len2 { break; } let now = map.remove(&(c1, c2)).unwrap(); if c1 < len1 { let next = now + (p - coupons[0][c1]).max(0); let value = map.entry((c1 + 1, c2)).or_insert(1 << 30); *value = (*value).min(next); } if c2 < len2 { let next = now + p / 100 * (100 - coupons[1][c2]); let value = map.entry((c1, c2 + 1)).or_insert(1 << 30); *value = (*value).min(next); } } } let ans = map.values().min().unwrap() + sum; println!("{}", ans); }