Proficient.
Put your skills to the test.

Problem summary

Unit-time jobs become available at sorted times reqTimes. GPUs have sorted per-job costs gpuCosts. Assign every job after its release, at most one job per GPU per second, minimizing completion time F multiplied by total cost S.

Source clarification. The official grader explicitly requires GNU __int128 because F·S can exceed signed 64-bit range; the published implementation preserves that exact interface.

Constraints

1 ≤ N ≤ 10,000,000; 1 ≤ M ≤ N; 0 ≤ release times ≤ N; 1 ≤ costs ≤ 2N; up to 5 independent calls.

Worked example

An independently prepared example for this explanation.

1
8 4
1 2 2 6
0 0 0 0 1 2 2 2

39

Solution analysis

1. For a fixed deadline F, use each GPU during a suffix of the seconds before F. One optimal schedule has nondecreasing GPU usage over time: moving a job into a later unused slot never violates a release time. Process jobs in decreasing release order, assigning each to the cheapest GPU whose suffix still has an available slot. At release t, a GPU can contain at most F−t of the jobs processed so far.
2. First construct this greedy skyline for F0=maxRelease+1, temporarily allowing as many GPUs as needed. For each distinct release time, restart the cheapest-GPU pointer at zero; fill its count up to F0−t, then advance. This takes O(N): the pointer advances only after a job fills a GPU at that release time, and every restart is constant work. The resulting GPU counts are nonincreasing.
3. When F increases by one, extend every nonempty GPU suffix by one slot. This creates K excess jobs, where K is the current GPU count. Delete K slots from the most expensive suffixes, popping an empty last suffix and continuing if necessary. This is the new fixed-deadline greedy skyline: the extra earlier slot on each retained GPU supplies exactly its newly available capacity, and removing the most expensive slots minimizes cost.
4. A shared offset adds one to every count in constant time. Only tail counts are explicitly decreased. Maintain the total cost of the first M GPUs and cost prefix sums; a skyline is feasible exactly when at most M GPUs remain. Test F·S whenever feasible, and stop once one GPU remains because all later deadlines have the same minimum possible cost N·C[0]. For the sample, F=3 gives counts 3,3,2 on costs 1,2,2, hence S=13 and product 39.

Why it works

At a fixed deadline, reverse-time greedy is optimal by exchange: the latest unreassigned job must occupy a slot no earlier than its release; replacing its selected slot by the cheapest available eligible suffix slot preserves feasibility for all earlier-release jobs and never increases cost. This establishes the skyline construction. Increasing the deadline gives one new slot to every used GPU. The reverse-time greedy skyline for the new deadline keeps these available cheap slots and discards exactly K excess slots from the most expensive suffixes; equivalently, earlier jobs move from expensive GPUs into the newly available cheaper slots. Thus induction over F preserves the optimal fixed-deadline counts. A skyline requiring more than M GPUs is infeasible; once it fits, its computed cost is the minimum for that deadline. Every relevant deadline from maxRelease+1 through the first single-GPU skyline is tested. Beyond that point cost cannot be below N·C[0], so the minimum tested product is globally optimal.

Watch out. Do not access costs beyond M while constructing an initially infeasible unlimited-GPU skyline. Empty a suffix using count+offset. Reinitialize every call and preserve the reference signature.

The official interface requires GNU __int128 and #include "gpus.h". This is an intentional nonportable exception to standard C++17: compile with GNU g++ -std=c++17 -O2 -Wall -Wextra together with the supplied grader/header, without -pedantic-errors. There is no main in the submission.

#include"gpus.h"
#include<vector>
#include<algorithm>
__int128 solveGpus(std::vector<int>&gpuCosts,std::vector<int>&reqTimes){
    int n=static_cast<int>(reqTimes.size());
    int m=static_cast<int>(gpuCosts.size());
    int finish=reqTimes.back()+1;
    std::vector<long long>counts;
    int previous=-1;
    int gpu=0;
    for(int i=n-1;i>=0;--i){
        if(reqTimes[i]!=previous){
            previous=reqTimes[i];
            gpu=0;
        }
        if(gpu==static_cast<int>(counts.size())){
            counts.push_back(0);
        }
        ++counts[gpu];
        if(counts[gpu]==finish-reqTimes[i]){
            ++gpu;
        }
    }
    std::vector<long long>prefix(m+1,0);
    for(int i=0;i<m;++i){
        prefix[i+1]=prefix[i]+gpuCosts[i];
    }
    long long sum=0;
    for(int i=0;i<std::min(m,static_cast<int>(counts.size()));++i){
        sum+=counts[i]*gpuCosts[i];
    }
    long long offset=0;
    __int128 best=-1;
    while(true){
        int used=static_cast<int>(counts.size());
        if(used<=m){
            __int128 value=static_cast<__int128>(finish)*sum;
            if(best==-1||value<best){
                best=value;
            }
        }
        if(used==1){
            break;
        }
        ++finish;
        ++offset;
        sum+=prefix[std::min(used,m)];
        long long remove=used;
        // A common offset adds one slot to every nonempty GPU suffix.
        // Remove the excess jobs from the most expensive suffixes first.
        while(remove>0){
            int last=static_cast<int>(counts.size())-1;
            long long available=counts.back()+offset;
            long long take=std::min(remove,available);
            if(last<m){
                sum-=take*gpuCosts[last];
            }
            remove-=take;
            counts.back()-=take;
            if(counts.back()+offset==0){
                counts.pop_back();
            }
        }
    }
    return best;
}