TOI15: Minimum Load Requirement

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

typedef long long lli;
typedef tuple<int, int, int> tiii;

const int N = 10;
const int S = 1e7;

vector<tiii> liftAssistPairs;
int lift[N + 1], assist[N + 1], student[S + 1], limTime[N + 1], divide[N + 2];
bool liftChosen[N + 1], assistChosen[N + 1];

int main(){

    int n, nStudent, Q;
    scanf("%d%d%d", &n, &nStudent, &Q);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &lift[i]);
    }
    for(int i = 1; i <= n; ++i){
        scanf("%d", &assist[i]);
    }
    for(int i = 1; i <= nStudent; ++i){
        scanf("%d", &student[i]);
    }

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            liftAssistPairs.emplace_back(lift[i] - assist[j], i, j);
        }
    }
    sort(liftAssistPairs.begin(), liftAssistPairs.end());

    for(int q = 1; q <= Q; ++q){
        scanf("%d", &limTime[q]);
    }
    for(int q = 1; q <= Q; ++q){
        for(int i = 1; i <= n; ++i){
            liftChosen[i] = false;
            assistChosen[i] = false;
            scanf("%d", &divide[i]);
        }
        divide[n + 1] = nStudent + 1;
        vector<int> req;
        bool broken = false;
        for(int i = 1; i <= n; ++i){
            int ans = 2e9 + 200;
            int l = 0;
            int r = 2e9 + 200;
            while(l <= r){
                int m = ((lli)l + r) / 2;
                int sum = 0;
                int cnt = 0;
                for(int j = divide[i]; j < divide[i + 1]; ++j){
                    if(student[j] > m){
                        cnt = 1e9;
                        break;
                    }
                    if(sum + student[j] > m){
                        sum = 0;
                    }
                    if(sum == 0){
                        ++cnt;
                    }
                    sum += student[j];
                }
                if(cnt <= limTime[q]){
                    ans = min(ans, m);
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            req.push_back(ans);
        }
        sort(req.begin(), req.end());
        int j = lower_bound(liftAssistPairs.begin(), liftAssistPairs.end(), tiii(req[0], 0, 0)) - liftAssistPairs.begin();
        for(int i = 0; i < req.size(); ++i){
            while(j < liftAssistPairs.size() && (get<0>(liftAssistPairs[j]) < req[i] ||
                liftChosen[get<1>(liftAssistPairs[j])] || assistChosen[get<2>(liftAssistPairs[j])])){
                ++j;
            }
            if(j == liftAssistPairs.size()){
                broken = true;
                break;
            }
            liftChosen[get<1>(liftAssistPairs[j])] = true;
            assistChosen[get<2>(liftAssistPairs[j])] = true;
        }
        if(broken){
            cout << "F\n";
        } else {
            cout << "P\n";
        }
    }

    return 0;
}