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

// Brute-force O(n*(n + log n))
// And a heuristic... :(

static const unsigned int MAX_N = 1000 * 1000;

typedef long long ll;
struct elem_t {
    ll current;
    ll tempo;
    bool taken;
};

int n;

elem_t arr[MAX_N];

void loadData()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &arr[i].tempo, &arr[i].current);
        arr[i].taken = false;
    }
}

int main()
{
    loadData();

    std::sort(std::begin(arr), std::begin(arr) + n,
            [](const elem_t & a, const elem_t & b) -> bool {
                return a.tempo < b.tempo;
            });

    ll sum = 0;

    for (int i = 0; i < n; i++) {
        int maxcand = -1;
        ll maxval = -1;

        for (int j = 0; j < n; j++) {
            if (arr[j].taken)
                continue;

            if (maxval < arr[j].current) {
                maxval = arr[j].current;
                maxcand = j;
            }
        }

        sum += maxval;
        arr[maxcand].taken = true;

        for (int j = 0; j < maxcand; j++) {
            arr[j].current += arr[maxcand].tempo;
        }

        for (int j = maxcand + 1; j < n; j++) {
            arr[j].current += arr[j].tempo;
        }

        printf("%lld\n", sum);
    }

    return 0;
}