1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
use std::{collections::BinaryHeap, io};

pub fn main() -> io::Result<()> {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf)?;

    let [n, k] = buf.trim().split_whitespace().map(|x| x.parse().unwrap()).collect::<Vec<i32>>()[..] else {
        panic!("");
    };
    buf.clear();

    io::stdin().read_line(&mut buf)?;
    let mut data: Vec<i32> = buf.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();

    let mut heap: BinaryHeap<(i32,usize)> = BinaryHeap::new();
    for (idx, val) in data.iter().copied().enumerate() {
        heap.push((val, idx));
    }

    // eprintln!("data: {:?}",data);
    // eprintln!("heap: {:?}",heap);

    let mut res = 0;
    while let Some((val, idx)) = heap.pop() {
        if val == data[idx] {
            if idx > 0 {
                let new = data[idx-1].max(val - k);
                if new != data[idx-1] {
                res += new - data[idx-1];
                data[idx-1] = new;
                heap.push((new, idx-1));
                }
            }
            if idx < (n as usize)-1 {
                let new = data[idx+1].max(val - k);
                if new != data[idx+1] {
                res += new - data[idx+1];
                data[idx+1] = new;
                heap.push((data[idx+1], idx+1));
                }
            }
        }
    }
    println!("{res}");

    Ok(())
}