001.rs

use proconio::input;
use proconio::marker::Usize1;
use num::integer::gcd;
use std::collections::{HashMap, HashSet, BinaryHeap};



fn main() {
    input!{
        n: i64,
        l: i64,
        k: i64,
        a: [Usize1; n]
    }

    let check_possible = move |score: i64|{
        // 左からscore以上のながさになるように切っていく。
        // 切りおわったときに、所定回数より小さかったらfalse
        // 切りおわって右端の長さがscore未満でもfalse
        // いずれでもないときtrue
        let mut current_len: i64 = 0;
        let mut cut_num: i64 = 0;
        for ai in a{
            current_len += ai as i64;
            if current_len >= score{
                // きる
                cut_num += 1;
                current_len = 0;
            }
        }
        // この時点でcurrent_lenが右端の長さ
        if cut_num < k{
            return false;
        }
        if current_len < score{
            return false;
        }

        return true;
    };

    let mut ok: i64 = 0;
    let mut ng: i64 = n as i64 + 1;
    while (ng - ok).abs() > 1{
        let piv = (ng + ok)/2;
        let f = &check_possible;
        if f(piv){
            ok = piv;
        }else{
            ng = piv;
        }
    }

    println!("{}", ok);


}