AtCoder Beginner Contest 319 D

https://atcoder.jp/contests/abc319/tasks/abc319_d

Wが決まれば行数は簡単に決まるので、Wを二分探索すればよいですが、Wを変えても行数が変わらないことがあるのがいやらしいですね。

// Minimum Width
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (i32, Vec<i64>) {
    let v: Vec<i32> = read_vec();
    let M = v[1];
    let L = read_vec();
    (M, L)
}

fn num_rows(W: i64, L: &Vec<i64>) -> i32 {
    let mut r: i32 = 0;
    let mut c: i64 = 0;
    for (i, &l) in L.iter().enumerate() {
        c += l + (if i == 0 { 0 } else { 1 });
        if c > W {
            c = l;
            r += 1
        }
    }
    r + 1
}

fn bin_search(first: i64, last: i64, M: i32, L: &Vec<i64>) -> i64 {
    if first == last - 1 {
        first
    }
    else {
        let mid = (first + last) / 2;
        if num_rows(mid-1, L) > M {
            bin_search(mid, last, M, L)
        }
        else {
            bin_search(first, mid, M, L)
        }
    }
}

fn f(M: i32, L: Vec<i64>) -> i64 {
    let min_W = L.iter().map(|&l| l).max().unwrap() as i64;
    let max_W = L.iter().sum::<i64>() + L.len() as i64 - 1;
    bin_search(min_W, max_W + 1, M, &L)
}

fn main() {
    let (M, L) = read_input();
    println!("{}", f(M, L));
}