Proficient.
Put your skills to the test.

Problem summary

Each student wants one film. A film has only one copy: transfer takes T and watching takes L; it cannot be watched while transferred. The server and each computer can participate in at most m simultaneous transfers. Find when everyone can finish.

Constraints

1 ≤ n,m,T,L ≤ 1,000,000; identifiers lie in 1…n.

Worked example

An independently prepared example for this explanation.

5 3 1 2
2 5 3 2 5

6

Solution analysis

1. All students wanting the same film must form a chain: download, watch, transfer, watch, and so on. If that film has c viewers and its initial transfer starts at s, its earliest finish is s+c(T+L).
2. Only the initial server transfers compete for a shared resource. Once a film leaves the server, give it a chain of distinct viewers; each viewer handles only this film. The server can start m films at times 0,T,2T,… . Sort viewer counts in decreasing order and assign the longest chains the earliest slots.
3. In the example the counts are 2,2,1. All three initial transfers start at time 0, and the largest chain finishes at 2(1+2)=6. If there are more than m distinct films, later groups receive the additional start delay floor(i/m)T.

Why it works

Compress any server schedule into successive batches without delaying a film. If an earlier slot contains a shorter chain than a later slot, exchanging the two cannot increase the larger completion time: the longer chain benefits from the earlier start, and the shorter one cannot exceed the longer chain’s former completion. Repeated exchanges give the sorted schedule. The constructed independent viewer chains realize every computed completion time.

Watch out. Count distinct films rather than all students as server jobs. Watching does not occupy a server transfer slot. Use 64-bit arithmetic for the finishing time.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,slots;
    long long transfer,watching;
    cin>>n>>slots>>transfer>>watching;
    vector<int>count(n+1);
    for(int i=0;i<n;i++){
        int film;
        cin>>film;
        count[film]++;
    }
    sort(count.rbegin(),count.rend());
    long long answer=0;
    for(int i=0;i<n&&count[i]>0;i++){
        // Longer viewer chains receive earlier server slots.
        answer=max(answer,(i/slots)*transfer+count[i]*(transfer+watching));
    }
    cout<<answer<<'\n';
}