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
#include<bits/stdc++.h>
using namespace std;
int n, c;
pair<int, int> x[1000005];
long long dp[1000005][2], wart[1000005], wart2[1000005];
vector<int> v;
int main()
{
    cin >> n >> c;
    for(int i = 1; i <= n; i++) cin >> x[i].first >> x[i].second;
    sort(x + 1, x + 1 + n);
    int last = n + 1;
    for(int i = n; i > 0; i--) //zamiast i + 1 dajemy indeks ostatniego chlopa ktory ma inny wie niz my + zmienic cos w wart[typ[i]] bo to moze trzymac wartosc typu ktory ustawil gosc o tej samej wielkosci co my
    {
        dp[i][0] = max(dp[i + 1][0], dp[i + 1][1]);
        dp[i][1] = max(dp[last][0] - c, max(dp[last][1] - c, wart[x[i].second])) + x[i].first;
        wart2[x[i].second] = max(wart2[x[i].second], dp[i][1]);
        v.push_back(x[i].second);
        if(x[i].first != x[i - 1].first)
        {
            last = i;
            for(auto el : v)
            {   
                wart[el] = max(wart[el], wart2[el]);
                wart2[el] = 0;
            }
            v.clear();
        }
    }

    cout << max(dp[1][0], dp[1][1]);
}

/* 
3 5
1 1
3 2
4 3
*/