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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    LL n, c=(cin>>n>>c, c), a1, a2, w;
    vector<LL> max_wyn_wzorku(500001, 0);
    LL max_wyn_total=0;
    vector<pair<int, LL>> ta_wys; //wzorek, wynik
    for(int i=0; i<n; i++, a1=a2){
        cin>>a2>>w;
        LL x=0;
        if(a2!=a1){
            for(int i=0; i<ta_wys.size(); i++){
                max_wyn_total=max(max_wyn_total, ta_wys[i].second);
                max_wyn_wzorku[ta_wys[i].first]=max(max_wyn_wzorku[ta_wys[i].first], ta_wys[i].second);
            }
            ta_wys.clear();
        }
        x=max(max_wyn_wzorku[w], max_wyn_total-c)+a2;
        ta_wys.push_back({w, x});
    }
    for(int i=0; i<ta_wys.size(); i++){
        max_wyn_total=max(max_wyn_total, ta_wys[i].second);
        max_wyn_wzorku[ta_wys[i].first]=max(max_wyn_wzorku[ta_wys[i].first], ta_wys[i].second);
    }
    cout<<max_wyn_total;
    return 0;
}