Expert.
Put your skills to the test.

Problem summary

There are L seats in one row and N passengers. A seated passenger i gains A[i], plus B[i] for every consecutive empty seat between them and the next passenger or row end on either side. A standing passenger gains zero. For each K=1..N, maximize total enjoyment with exactly K seated passengers.

Constraints

1 ≤ N ≤ 100,000; 1 ≤ L ≤ 200,000; 0 < A[i],B[i] < 10⁹. Values use 64-bit arithmetic.

Worked example

The second official example, with whitespace restored from the PDF.

3 3
1 2
3 4
5 100

205
112
9

Solution analysis

1. For a fixed seated set, every empty gap contributes its length times the sum of its adjacent passengers’ B-values; an end gap has only one adjacent passenger. Move all empty seats into a gap with maximum coefficient. For K≥2, place the two largest-B selected passengers next to that gap. The optimum is ΣA+(L−K)(largest B+second-largest B). For K=1 it is A+(L−1)B.
2. Sort passengers by decreasing A. Mark the two passengers bordering the empty gap. Every other selected passenger is chosen solely for A, so the unmarked K−2 passengers can be the highest-A passengers not marked. Consequently an optimal solution is covered by three cases: all selected passengers are the top K; the top K−1 plus one outside endpoint; or the top K−2 plus two outside endpoints.
3. Write x=L−K and line_i(x)=A[i]+B[i]x. Case 1 uses prefix sums of A and the two largest prefix B-values. Case 2 adds the maximum line in the suffix starting at K−1 to the A-sum and largest B of the preceding prefix. Case 3 adds the two highest distinct lines in the suffix starting at K−2. Query the best index, then query the ranges before and after that index to get the second best.
4. A segment tree stores a static upper convex hull of lines in every node. Sort slopes, keep the highest intercept for equal slopes, and remove a middle line when its neighboring intersection order is invalid. Binary search adjacent hull values for a maximum at x. This deterministic range structure avoids random sampling and supports excluding the first maximum’s index.
5. Worked example: A=(1,3,5), B=(2,4,100), L=3. For K=1 choose passenger 3: 5+2×100=205. For K=2 choose passengers 2 and 3 with one empty seat between them: 3+5+4+100=112. For K=3 there are no empty seats, giving 1+3+5=9.

Why it works

Linear gap contributions imply all empty seats can be concentrated in a best gap. After fixing its at most two endpoints, exchanging any other selected passenger for a larger-A unselected passenger cannot decrease enjoyment. This yields the three exhaustive prefix/suffix cases. Each line query evaluates precisely A+xB for the endpoint, and excluding the first best index gives two distinct passengers. Exact hull intersection comparisons and maximum queries preserve the optimal values.

Watch out. Do not count each empty seat for every passenger: only its immediate neighboring passengers benefit. K=1 has one B coefficient, not two. The two best lines must belong to distinct passengers. Equal slopes need deduplication within each hull, but not deletion of passengers from the underlying index ranges.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
struct Passenger{
    long long sitting,space;
};
struct Line{
    long long slope,intercept;
    int index;
    long long value(long long x)const{
        return slope*x+intercept;
    }
};
class RangeHull{
    vector<vector<Line>>hull;
    const vector<Passenger>&people;
    int n;
    void build(int node,int left,int right){
        vector<Line>lines;
        for(int i=left;i<=right;++i){
            lines.push_back({people[i].space,people[i].sitting,i});
        }
        sort(lines.begin(),lines.end(),[](const Line&a,const Line&b){
            if(a.slope!=b.slope){
                return a.slope<b.slope;
            }
            return a.intercept>b.intercept;
        });
        auto&result=hull[node];
        for(const Line&line:lines){
            if(!result.empty()&&result.back().slope==line.slope){
                continue;
            }
            while(result.size()>=2){
                const Line&a=result[result.size()-2];
                const Line&b=result.back();
                // Intersection(a,b) >= intersection(b,line): b is never uniquely best.
                long long lhs=(a.intercept-b.intercept)*(line.slope-b.slope);
                long long rhs=(b.intercept-line.intercept)*(b.slope-a.slope);
                if(lhs<rhs){
                    break;
                }
                result.pop_back();
            }
            result.push_back(line);
        }
        if(left<right){
            int middle=(left+right)/2;
            build(node*2,left,middle);
            build(node*2+1,middle+1,right);
        }
    }
    pair<long long,int>query(int node,int left,int right,int from,int to,long long x)const{
        if(to<left||right<from){
            return {numeric_limits<long long>::lowest()/4,-1};
        }
        if(from<=left&&right<=to){
            const auto&lines=hull[node];
            int low=0;
            int high=static_cast<int>(lines.size())-1;
            while(low<high){
                int middle=(low+high)/2;
                if(lines[middle].value(x)<=lines[middle+1].value(x)){
                    low=middle+1;
                }
                else{
                    high=middle;
                }
            }
            return {lines[low].value(x),lines[low].index};
        }
        int middle=(left+right)/2;
        return max(
            query(node*2,left,middle,from,to,x),query(node*2+1,middle+1,right,from,to,x));
    }
    public:
    explicit RangeHull(const vector<Passenger>&p)
        :hull(4*p.size()),people(p),n(static_cast<int>(p.size())){
        build(1,0,n-1);
    }
    pair<long long,int>maximum(int left,int right,long long x)const{
        return query(1,0,n-1,left,right,x);
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,seats;
    cin>>n>>seats;
    vector<Passenger>people(n);
    for(Passenger&p:people){
        cin>>p.sitting>>p.space;
    }
    sort(people.begin(),people.end(),[](const Passenger&a,const Passenger&b){
        return a.sitting>b.sitting;
    });
    vector<long long>prefix(n+1),largest(n+1),second(n+1);
    for(int i=0;i<n;++i){
        prefix[i+1]=prefix[i]+people[i].sitting;
        largest[i+1]=max(largest[i],people[i].space);
        second[i+1]=max(second[i],min(largest[i],people[i].space));
    }
    RangeHull ranges(people);
    for(int count=1;count<=n;++count){
        if(count>seats){
            cout<<0<<'\n';
            continue;
        }
        long long empty=seats-count;
        if(count==1){
            cout<<ranges.maximum(0,n-1,empty).first<<'\n';
            continue;
        }
        // Neither, one, or both endpoints of the empty block come from outside the top-A prefix.
        long long answer=prefix[count]+empty*(largest[count]+second[count]);
        answer=max(answer,
            prefix[count-1]+empty*largest[count-1]+ranges.maximum(count-1,n-1,empty).first);
        int from=count-2;
        auto first=ranges.maximum(from,n-1,empty);
        auto other=max(
            ranges.maximum(from,first.second-1,empty),ranges.maximum(first.second+1,n-1,empty));
        answer=max(answer,prefix[count-2]+first.first+other.first);
        cout<<answer<<'\n';
    }
}