結果
| 問題 | No.3509 Get More Money |
| コンテスト | |
| ユーザー |
 akakimidori
|
| 提出日時 | 2026-04-18 12:11:50 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 139 ms / 2,000 ms |
| コード長 | 5,543 bytes |
| 記録 | |
| コンパイル時間 | 4,699 ms |
| コンパイル使用メモリ | 199,804 KB |
| 実行使用メモリ | 17,664 KB |
| 最終ジャッジ日時 | 2026-04-18 12:12:09 |
| 合計ジャッジ時間 | 19,156 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 60 |
コンパイルメッセージ
warning: type alias `Map` is never used --> src/main.rs:84:6 | 84 | type Map<K, V> = BTreeMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default warning: type alias `Set` is never used --> src/main.rs:85:6 | 85 | type Set<T> = BTreeSet<T>; | ^^^ warning: type alias `Deque` is never used --> src/main.rs:86:6 | 86 | type Deque<T> = VecDeque<T>; | ^^^^^
ソースコード
// dp[j]: j個ジュエルを保有してる時の最大値
//
// ep[j] = max_{0 <= p <= B} (dp[j-p] - Ap)
// fp[j] = max_{0 <= p <= D} (dp[j+p] + Cp)
// fp[0..=k] のみ残す
//
// というイメージの操作をできるといい
fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
let t: u32 = sc.next();
for _ in 0..t {
let n = sc.next::<usize>();
let k: i64 = sc.next();
let a = sc.next_vec::<i64>(n);
let b = sc.next_vec::<i64>(n);
let c = sc.next_vec::<i64>(n);
let d = sc.next_vec::<i64>(n);
let mut h = IntervalHeap::new();
let mut ans = 0;
let mut sum = 0;
for (((a, b), c), d) in a.into_iter().zip(b).zip(c).zip(d) {
h.push((a, b));
sum += b;
let mut v = 0;
while v < d && h.get_min().map_or(false, |p| p.0 < c) {
let (a, b) = h.pop_min().unwrap();
let sub = b.min(d - v);
ans += (c - a) * sub;
v += sub;
sum -= sub;
if sub < b {
h.push((a, b - sub));
}
}
if v > 0 {
h.push((c, v));
sum += v;
}
while sum > k {
let (a, b) = h.pop_max().unwrap();
let sub = (sum - k).min(b);
sum -= sub;
if b > sub {
h.push((a, b - sub));
}
}
}
writeln!(out, "{}", ans).ok();
}
}
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
use std::str::FromStr;
pub struct Scanner<'a> {
it: std::str::SplitWhitespace<'a>,
}
impl<'a> Scanner<'a> {
pub fn new(s: &'a String) -> Scanner<'a> {
Scanner {
it: s.split_whitespace(),
}
}
pub fn next<T: FromStr>(&mut self) -> T {
self.it.next().unwrap().parse::<T>().ok().unwrap()
}
pub fn next_bytes(&mut self) -> Vec<u8> {
self.it.next().unwrap().bytes().collect()
}
pub fn next_chars(&mut self) -> Vec<char> {
self.it.next().unwrap().chars().collect()
}
pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
(0..len).map(|_| self.next()).collect()
}
}
}
// ---------- end scannner ----------
use std::io::Write;
use std::collections::*;
type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;
fn main() {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
let mut sc = scanner::Scanner::new(&s);
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
run(&mut sc, &mut out);
}
// ---------- begin interval heap ----------
pub struct IntervalHeap<T> {
array: Vec<T>,
}
#[allow(dead_code)]
impl<T: Ord> IntervalHeap<T> {
pub fn new() -> Self {
IntervalHeap { array: vec![] }
}
pub fn len(&self) -> usize {
self.array.len()
}
pub fn push(&mut self, val: T) {
let a = &mut self.array;
let mut k = a.len();
a.push(val);
if k & 1 == 1 && a[k - 1] > a[k] {
a.swap(k - 1, k);
k -= 1;
}
IntervalHeap::up_heap(a, k);
}
pub fn get_min(&self) -> Option<&T> {
self.array.get(0)
}
pub fn get_max(&self) -> Option<&T> {
self.array.get(1).or_else(|| self.array.get(0))
}
pub fn pop_min(&mut self) -> Option<T> {
self.array.pop().map(|mut v| {
let a = &mut self.array;
if !a.is_empty() {
std::mem::swap(&mut a[0], &mut v);
let mut k = 0;
while 2 * k + 2 < a.len() {
let mut c = 2 * k + 2;
if c + 2 < a.len() && a[c] > a[c + 2] {
c += 2;
}
a.swap(k, c);
k = c;
}
if k + 1 < a.len() && a[k] > a[k + 1] {
a.swap(k, k + 1);
k += 1;
}
IntervalHeap::up_heap(a, k);
}
v
})
}
pub fn pop_max(&mut self) -> Option<T> {
self.array.pop().map(|mut v| {
let a = &mut self.array;
if a.len() >= 2 {
std::mem::swap(&mut a[1], &mut v);
let mut k = 1;
while 2 * k + 1 < a.len() {
let mut c = 2 * k + 1;
if c + 2 < a.len() && a[c] < a[c + 2] {
c += 2;
}
a.swap(k, c);
k = c;
}
if a[k - 1] > a[k] {
a.swap(k, k - 1);
k -= 1;
}
IntervalHeap::up_heap(a, k);
}
v
})
}
fn up_heap(a: &mut [T], mut k: usize) {
while k >= 2 {
let p = ((k >> 1) - 1) & !1;
if a[p] <= a[k] {
break;
}
a.swap(p, k);
k = p;
}
while k >= 2 {
let p = ((k >> 1) - 1) | 1;
if a[p] >= a[k] {
break;
}
a.swap(p, k);
k = p;
}
}
}
// ---------- end interval heap ----------