Proficient.
Put your skills to the test.

Problem summary

Students lie along a road at sorted positions x[i]. Student i pays v[i] per kilometer walked toward the origin. A bus at y[j]≤x[i] can bring the student directly home; its rental c[j] is paid only once even if several students share it. Find the optimum total cost for every prefix of students under this original shared-rental model.

Source clarification. The source has incompatible global and scored-subtask descriptions. Its official full general-model editorial is O(NM) for N≤20000,M≤1000, while the header permits100000 of each. Subtask2 explicitly changes billing so every student pays a bus rental separately, but stdin has no mode flag. Its second example prints10 34 58 for that changed model; the original shared-rental model gives10 24 48 for that same input. This page solves the original model only and does not claim full header-scale performance. Editorial: https://infos.infosbg.com/files/Contests/ETI/2022/B/analyses/B5_expedition_analysis.pdf

Constraints

The header lists N,M≤100000, positions and walking rates≤2^30, rents≤2^40; some bus is at or before the first student. The official general-model full subtask instead bounds N≤20000,M≤1000. Every required answer is≤2·10^18.

Worked example

Original statement sample.

6
1 3
2 10
3 100
4 100
5 15
6 10
3
2 5
4 9
8 3

8 28 44

Solution analysis

1. An optimum can assign students to nondecreasing bus indices. If an earlier student uses a farther bus than the next student, that next student can move to the already rented farther bus, walk no more, and avoid an extra rental. This removes the crossing assignment without increasing cost.
2. Let dp[j] be the best cost for the processed prefix when its last student uses bus j. The next student can reuse j without another rental, or start bus j after any smaller previous bus. A running prefix minimum of the previous DP row evaluates this second alternative in constant time per bus.
3. The transition is new[j]=(x−y[j])v+min(dp[j],min_{k<j}dp[k]+c[j]) for reachable buses. The first student may open any reachable bus from cost0. Rolling rows use O(N) memory. In the example, the first student walks to bus1 for8; the first two instead share bus2 for28; the third uses bus6 for16 extra, giving44. Saturating states above a safe sentinel prevents overflow in nonoptimal assignments.

Why it works

Removing crossing bus choices proves an optimum with nondecreasing bus indices exists. Such an optimum either continues the previous last bus or first opens a larger bus, exactly the two transition cases. The DP enumerates both and charges every rental once. Induction over the prefix length therefore gives the original shared-rental optimum.

Watch out. Never infer the different billing model merely because all walking rates are equal. Inputs have no model flag. Unreachable buses must have infinite DP cost. Nonoptimal intermediate assignments can exceed64-bit bounds unless clamped safely, despite the guarantee on optimal answers.

Complete implementation of the original shared-rental model. Complexity is O(NM); the official scored general-model full subtask uses N≤20000,M≤1000. This is not a100000×100000 algorithm, and the separate-pay subtask variant cannot be selected from the input alone.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const long long infinity=4000000000000000000LL;
long long safeAdd(long long a,long long b){
    if(a>=infinity-b){
        return infinity;
    }
    return a+b;
}
long long safeProduct(long long a,long long b){
    if(b!=0&&a>infinity/b){
        return infinity;
    }
    return a*b;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>position(n);
    vector<long long>rental(n);
    for(int j=0;j<n;j++){
        cin>>position[j]>>rental[j];
    }
    int students;
    cin>>students;
    vector<long long>previous(n,infinity);
    vector<long long>current(n,infinity);
    for(int i=0;i<students;i++){
        long long x,rate;
        cin>>x>>rate;
        long long earlier=i==0?0:infinity;
        long long answer=infinity;
        for(int j=0;j<n;j++){
            current[j]=infinity;
            if(position[j]<=x){
                long long open=safeAdd(earlier,rental[j]);
                long long walking=safeProduct(x-position[j],rate);
                current[j]=safeAdd(min(previous[j],open),walking);
                answer=min(answer,current[j]);
            }
            // Update after the transition: earlier buses exclude j itself.
            earlier=min(earlier,previous[j]);
        }
        previous.swap(current);
        if(i>0){
            cout<<' ';
        }
        cout<<answer;
    }
    cout<<'\n';
}