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
#include <iostream>
#include <map>
#include <set>
#include <vector>

struct Wieza {
    int wzorek;
    int64_t ocena;

    bool operator<(const Wieza&w) const {
        if (w.ocena != ocena) {
            return w.ocena < ocena;
        }
        return w.wzorek < wzorek;
    }

};

int wieza() {
    int liczbaKlockow;
    int64_t kara;

    std::cin >> liczbaKlockow >> kara;

    std::set<Wieza> wKolejnosci;
    std::map<int,Wieza> najpiekniejsze;
    std::vector<Wieza> oczekujace;
    std::vector<Wieza> stos;

    for (int i = 0; i < liczbaKlockow; ++i) {
        int64_t wielkosc;
        int wzorek;
        std::cin >> wielkosc >> wzorek;
        stos.push_back({wzorek, wielkosc});
    }

    oczekujace.push_back(stos[liczbaKlockow-1]);

    for (int i = liczbaKlockow-2; i >= -1 ; --i) {
        int64_t wielkosc;
        int wzorek;
        if (0 <= i) {
            wzorek = stos[i].wzorek;
            wielkosc = stos[i].ocena;
        } else {
            wielkosc = wzorek = -1'000'000;
        }

        if (wielkosc == oczekujace[0].ocena) {
            oczekujace.push_back({wzorek, wielkosc});
            continue;
        }

        std::map<int,Wieza> najpiekniejszaZNowym;

        for (auto &k: oczekujace) {

            auto poprzednia = najpiekniejsze.find(k.wzorek);
            if (poprzednia != najpiekniejsze.end()) {
                Wieza &w = poprzednia->second;
                najpiekniejszaZNowym[k.wzorek] = {k.wzorek, k.ocena + w.ocena};
            } else {
                najpiekniejszaZNowym[k.wzorek] = {k.wzorek, k.ocena};
            }

            for (auto &w: wKolejnosci) {
                Wieza nowa{k.wzorek, w.ocena + k.ocena - (w.wzorek == k.wzorek ? 0 : kara)};
                if (najpiekniejszaZNowym[k.wzorek].ocena < nowa.ocena) {
                    najpiekniejszaZNowym[k.wzorek] = nowa;
                }
                break;
            }
        }
        for (auto &k: oczekujace) {
            auto poprzednia = najpiekniejsze.find(k.wzorek);
            if (poprzednia == najpiekniejsze.end() || poprzednia->second.ocena < najpiekniejszaZNowym[k.wzorek].ocena) {
                najpiekniejsze[k.wzorek] = najpiekniejszaZNowym[k.wzorek];
                wKolejnosci.insert(najpiekniejszaZNowym[k.wzorek]);
            }
        }
        oczekujace.clear();
        oczekujace.push_back({wzorek, wielkosc});
    }
    Wieza najpiekniejsza{-1, 0};
    for (auto &p: najpiekniejsze) {
        Wieza &w = p.second;
        if (najpiekniejsza.ocena < w.ocena) {
            najpiekniejsza = w;
        }
    }
    std::cout << najpiekniejsza.ocena << std::endl;
    return 0;
}

int main() {
    // for (;;)
    wieza();
}