TOI17: Noodle

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const int inf = 2e9;
const int N = 1e5 + 10;
const int M = 1e2 + 10;
const int K = 4e3 + 10;
int n, m, k;
int ar[N];

bool Check(lli check){
    priority_queue <int, vector <int>, greater <int>> pq;
    int cnt = 0, sum = 0, sz = 0;
    for(int i=1;i<=n;i++){
        sum += ar[i];
        pq.push(ar[i]);

        if(pq.size() > k){
            sum -= pq.top();
            pq.pop();
        }

        if((lli) sum >= check and pq.size() == k){
            cnt ++;
            sum = 0;
            while(!pq.empty()) pq.pop();
        }
    }
    return cnt >= m;
}

int main(){

    scanf("%d %d %d", &n, &m, &k);

    for(int i=1;i<=n;i++){
        scanf("%d", &ar[i]);
    }

    lli l = 0, r = inf, mx = -inf;
    while(l <= r){
        lli mid = (l + r) / 2;
        bool Ch = Check(mid);
        if(Ch) l = mid + 1, mx = max(mx, mid);
        else r = mid - 1;
    }

    printf("%lld", mx);

    return 0;
}

/*

Binary Search หา a ที่มากที่สุด
โดย a คือผลรวมขั้นต่ำที่ทำให้สามารถเลือกได้ k ตัว เป็นจำนวน m ช่วง

ในการเลือก k ตัวให้ได้ m ช่วงจะนำ priority queue มาใช้โดยให้เรียงจากน้อยไปมาก (เพื่อให้ดึงตัวที่น้อยที่สุดออกมา เพราะ หากครบ k ตัวแล้ว sum ไม่สามารถทำให้ >= check ได้แปลว่า หากมีตัวที่มากกว่าตัวที่น้อยที่สุดแล้ว ควรเอาตัวที่น้อยที่สุดนั้นออกไป)

เช่น A > B > C > D, sum = A + B + C + D
ใน  pq : D C B A มีตัวใหม่เข้ามาที่มากกว่า D ให้ดึง D (ลบ D ออกจาก sum ด้วย, sum -= D)

*/