Intermediate.
Put your skills to the test.

Problem summary

N DVDs must be recorded using K independent computers. Computer i takes Ti minutes per DVD, and the video file is already present on every computer. All computers can start immediately and operate simultaneously. Find the earliest time when all N DVDs can be finished.

Constraints

1 ≤ N, K ≤ 100,000; 1 ≤ Ti ≤ 100,000.

Worked example

Official statement sample.

3 2
10 15

20

Solution analysis

1. In t minutes, computer i finishes floor(t/Ti) discs. Add these capacities: t is sufficient exactly when their sum reaches N. Capacity never decreases as t grows, so the first sufficient time can be found by binary search.
2. Use the inclusive search interval [0, N·min(Ti)]. Its upper endpoint is feasible because the fastest computer alone can finish everything there. For a midpoint, keep the left half including the midpoint if it is feasible; otherwise discard it and everything earlier.
3. For three discs and times 10 and 15, time 19 yields only 1+1 = 2 discs, whereas time 20 yields 2+1 = 3. Thus the answer is 20. The implementation stops counting as soon as N is reached and uses long long for times.

Why it works

By time t, each computer can complete at most floor(t/Ti) discs, and independent continuous recording attains all these capacities. Their sum therefore characterizes feasibility. This predicate is monotone; binary search preserves a feasible right endpoint and discards only times that cannot be the first feasible one. The endpoints eventually meet at the minimum.

Watch out. The video is already on every computer: no initial copying delay is needed. N·min Ti can reach 10^10, exceeding int. Count completed discs, not fractions of discs.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    long long discs;
    int computers;
    cin>>discs>>computers;
    vector<int>recordingTime(computers);
    for(int&time:recordingTime){
        cin>>time;
    }
    long long left=0;
    long long right=discs**min_element(recordingTime.begin(),recordingTime.end());
    while(left<right){
        long long middle=left+(right-left)/2;
        long long completed=0;
        for(int time:recordingTime){
            completed+=middle/time;
            // Further machines cannot change a successful feasibility test.
            if(completed>=discs){
                break;
            }
        }
        if(completed>=discs){
            right=middle;
        }
        else{
            left=middle+1;
        }
    }
    cout<<left<<'\n';
}