提出 #8494902

---

ソースコード 拡げる

// Practice AtCoder
// author: Leonardone @ NEETSDKASU

fn main() {
  let mut stdin = String::new();
  std::io::Read::read_to_string(
    &mut std::io::stdin(),
    &mut stdin).unwrap();
  let mut stdin = stdin.split_whitespace();
  let mut get = || stdin.next().unwrap();
  macro_rules! get {
    ($t:ty) => (get().parse::<$t>().unwrap());
    () => (get!(i64));
  }
  
  let n = get!(usize);
  let k = get!(usize);
  
  let mut ps = vec![0];
  let mut hs = vec![];
  for _ in 0..n {
    let h = get!();
    ps.push(h);
    hs.push(h);
  }
  ps.sort();
  let mut dp = vec![vec![vec![std::i64::MAX / 2; k+1]; n+1];n+1];
  dp[0][0][0] = 0;
  for i in 0..n {
    for lhi in 0..n+1 {
      for u in 0..k+1 {
        for hi in 0..n+1 {
          use std::cmp::{min,max};
          if hs[i] == ps[hi] {
            dp[i+1][hi][u] = min(dp[i+1][hi][u], dp[i][lhi][u]+max(0, ps[hi] - ps[lhi]));
          } else if u < k {
            dp[i+1][hi][u+1] = min(dp[i+1][hi][u+1], dp[i][lhi][u]+max(0, ps[hi] - ps[lhi]));
          }
        }
      }
    }
  }
  let ans = dp[n].iter().map(|x|x.iter().min().unwrap()).min().unwrap();
  println!("{}", ans);
}

提出情報

ジャッジ結果