IPST61: Chicken Tart

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;
typedef pair<int, int> pii;

const int N = 1e5;

int arr[N + 1], cntLeft[N + 2], cntRight[N + 2];
int nTart, limLen, nPiece, mxLen;

bool canDivide(lli m){
    lli sum = 0;
    int tartCnt = 0;
    int cnt = 0;
    bool broken = false;
    for(int i = 1; i <= nTart; ++i){
        if(broken){
            cntLeft[i] = 1e9;
            continue;
        }
        if(arr[i] > m){
            cntLeft[i] = 1e9;
            broken = true;
            continue;
        }
        if(sum + arr[i] > m || tartCnt + 1 > limLen){
            ++cnt;
            sum = 0;
            tartCnt = 0;
        }
        sum += arr[i];
        ++tartCnt;
        cntLeft[i] = cnt + 1;
    }
    sum = 0;
    tartCnt = 0;
    cnt = 0;
    broken = false;
    for(int i = nTart; i >= 1; --i){
        if(broken){
            cntRight[i] = 1e9;
            continue;
        }
        if(arr[i] > m){
            cntRight[i] = 1e9;
            broken = true;
            continue;
        }
        if(sum + arr[i] > m || tartCnt + 1 > limLen){
            ++cnt;
            sum = 0;
            tartCnt = 0;
        }
        sum += arr[i];
        ++tartCnt;
        cntRight[i] = cnt + 1;
    }

    int mn = 1e9;
    for(int i = mxLen; i <= nTart; ++i){
        mn = min(mn, cntLeft[i - mxLen] + cntRight[i + 1]);
    }
    if(mn <= nPiece - 1){
        return true;
    } else {
        return false;
    }
}

int main(){

    scanf("%d%d%d", &nTart, &limLen, &nPiece);
    lli sum = 0;
    for(int i = 1; i <= nTart; ++i){
        scanf("%d", &arr[i]);
        sum += arr[i];
    }
    mxLen = min(limLen, nTart - nPiece + 1);

    lli l = 0;
    lli r = sum;
    lli mn = sum;
    while(l <= r){
        lli m = (l + r) / 2;
        if(canDivide(m)){
            mn = min(mn, m);
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    cout << mn;

    return 0;
}