Painter’s Partition Problem

• Time : $O(nlog(sum(A) * B))$
• Space : $O(1)$

#include <bits/stdc++.h>
const int mod = 10000003;
bool helper(vector<int>& A, long long k, long long c, long long m) {
    long long count = 1, now = 0;
    for(int i = 0; i < A.size(); i++) {
        if(now + A[i] * m <= k) now += A[i] * m;
        else {
            now = A[i] * m;
            count += 1;
            if(now >= k) now = 0;
        }
    }
    return count <= c;
}
int Solution::paint(int A, int B, vector<int> &C) {
    long long l = *max_element(begin(C), end(C)) * B, r = 1ll * accumulate(begin(C), end(C), 0ll) * B, res = r;
    while(l <= r) {
        long long m = l + (r - l) / 2;
        bool pass = helper(C,m,A,B);
        if(pass) {
            res = min(res, m);
            r = m - 1;
        } else l = m + 1;
    }
    return res % mod;
}