GCJ2018-1A2: Bit Party

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

typedef long long lli;

const int C = 1000;

int pay[C + 1], pack[C + 1], mxBit[C + 1];
int nCashier, nRobot, bits;

bool canDivide(lli tme){
    vector<int> purchase;
    for(int i = 1; i <= nCashier; ++i){
        if(pack[i] >= tme){
            purchase.push_back(0);
            continue;
        }
        lli mx = (tme - pack[i]) / pay[i];
        if(mx >= mxBit[i]){
            purchase.push_back(mxBit[i]);
        } else {
            purchase.push_back(mx);
        }
    }
    sort(purchase.begin(), purchase.end(), greater<int>());
    lli sum = 0;
    for(int i = 0; i < nRobot; ++i){
        sum += purchase[i];
    }
    if(sum >= bits){
        return true;
    } else {
        return false;
    }
}

int main(){

    int Q;
    scanf("%d", &Q);
    for(int q = 1; q <= Q; ++q){
        cout << "Case #" << q << ": ";
        scanf("%d%d%d", &nRobot, &bits, &nCashier);
        for(int i = 1; i <= nCashier; ++i){
            scanf("%d%d%d", &mxBit[i], &pay[i], &pack[i]);
        }
        lli l = 1;
        lli r = 2e18;
        lli mn = 2e18;
        while(l <= r){
            lli m = (l + r) / 2;
            if(canDivide(m)){
                mn = min(mn, m);
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        cout << mn << '\n';
    }

    return 0;
}