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
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair < LL, LL > PII;

const int N = 1e6 + 7;

int n;
LL dp[N][2];
PII t[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld%lld", &t[i].first, &t[i].second);
    sort(t + 1, t + n + 1);
    bool p = 0, q = 1;
    for(int i = 1; i <= n; i++)
    {
        swap(p, q);
        for(int j = i; j <= n; j++)
            dp[j][p] = max(dp[j - 1][p], dp[j - 1][q] + t[j].second + t[j].first * (i - 1));
        printf("%lld\n", dp[n][p]);
    }
    return 0;
}