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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 #include using namespace std; #define FOR(i,n) for(int i=0; i < int(n); ++i) #define FO(i,a,b) for(int i=int(a); i=int(a); --i) typedef long long ll; typedef pair pii; typedef vector vi; typedef vector vvi; typedef vector vpii; #define siz size()*1LL #define fi first #define se second #define ASS assert #define remin(a,b) a=min(a,b) #define remax(a,b) a=max(a,b) #define ALL(c) (c).begin(), (c).end() #define NL '\n' #define D if(0) #define cerr if(0)cerr const int N = 1e6+9; int n; vector> in; int main(){ ios_base::sync_with_stdio(0); cin >> n; in.resize(n); FOR(i,n){ cin >> in[i].fi >> in[i].se; } sort(ALL(in)); ll total_val = 0; FOR(i,n){ total_val += in[i].fi*i + in[i].se; } vector sol(n); sol[n-1] = total_val; vector used(n); vector cpos(n); FOR(i,n) cpos[i] = i; ll cval = total_val; FOR(iter,n-1){ ll sum_a = 0; ll strata_min = LLONG_MAX; int strata_min_arg = -1; OF(i,0,n){ if(used[i])continue; ll strata = sum_a + in[i].fi * cpos[i] + in[i].se; if(strata < strata_min){ strata_min = strata; strata_min_arg = i; } sum_a += in[i].fi; } used[strata_min_arg] = 1; cval -= strata_min; FO(i,strata_min_arg,n) cpos[i]--; sol[n-1-1-iter] = cval; } FOR(i,n){ cout << sol[i] << NL; } D{ cout.flush(); ll max_b = -LLONG_MAX; FOR(i,n) remax(max_b, in[i].se); D assert(cval == max_b); } return 0; }