1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//Lukasz Janeczko Krakow
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    int n, ind;
    cin >> n;
    vector < pair <long long,long long> > Mushrooms(n);
    for(int i=0; i<n; i++)
        cin >> Mushrooms[i].first >> Mushrooms[i].second;
    sort(Mushrooms.begin(),Mushrooms.end());
    long long s1=0, s2; bool Taken[n]; vector <long long> Cur(n+1,2100000000ll*100000000);
    for(int i=0; i<n; i++)
        {
            Taken[i]=false;
            if(Mushrooms[i].second>s1)
                {
                    s1=Mushrooms[i].second;
                    Cur[0]=s2=Mushrooms[i].first;
                    ind=i;
                }
        }
    Cur[n]=2100000000ll*100000000;
    Taken[ind]=true;
    cout << s1 <<endl;
    for(int g=1; g<n; g++)
        {
            int i=0, j=-1; long long newsume=0, cursume=0;
            while(i<n && j<g)
                {
                    while(i<n && Taken[i])
                        i++;
                    if(i<n)
                        while(j<g && Cur[j+1]<=Mushrooms[i].first)
                            {
                                cursume+=Cur[j+1];
                                j++;
                            }
                    while(i<n && Cur[j+1]>Mushrooms[i].first)
                        {
                            if(!Taken[i] && Mushrooms[i].second+Mushrooms[i].first*(j+1)+(s2-cursume)>newsume)
                                {
                                    ind=i;
                                    newsume=Mushrooms[i].second+Mushrooms[i].first*(j+1)+(s2-cursume);
                                }
                            i++;
                        }
                }
            Taken[ind]=true;
            s1+=newsume;
            s2+=Mushrooms[ind].first;
            Cur[g]=Mushrooms[ind].first;
            int p=g-1;
            while(p>=0 && Cur[p]>Cur[p+1])
                {
                    swap(Cur[p],Cur[p+1]);
                    p--;
                }
            cout << s1 <<endl;
        }
    return 0;
}