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
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1000*1000;

vector < pair <long long,long long> > F;
int Odw[N];

void Wczytaj(int n){
	int i;
	long long a,b;
	for(i=0; i<n; i++){
		scanf("%lld%lld", &a,&b);
		F.push_back(make_pair(a,b));
	}
}

void Wypisz(int n){
	int i,j,k;
	long long res,l_uzytych,a_res,aa_res,suma;
	res = 0;
	for(i=0; i<n; i++){
		suma = 0;
		for(j=n-1; j>=0; j--) if(Odw[j]) suma += F[j].first;
		k = -1; a_res = -1;
		l_uzytych = 0; 
		for(j=0; j<n; j++){
			if(!Odw[j]){
				aa_res = l_uzytych*F[j].first+F[j].second+suma;
				if(aa_res > a_res) {a_res = aa_res; k = j;};
			}
			else{
				l_uzytych++;
				suma -= F[j].first;
			}
		}
		res += a_res;
		printf("%lld\n", res);
		Odw[k] = 1;
	}
}

int main(){
	int n;
	scanf("%d", &n);
	Wczytaj(n);
	sort(F.begin(),F.end());
	Wypisz(n);
	return 0;
}