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 <iostream>
using namespace std;

int tab[500'007][2];
int dp[500'007];
int naj[500'007][2];

main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k, odp=0, naj_in_all=0, naj_in_all2=0;
    cin>>n>>k;
    for(int a=1; a<=n; a++)
        cin>>tab[a][0]>>tab[a][1];
    for(int a=1; a<=n; a++)
    {
        dp[a]=tab[a][0];

        if(tab[naj_in_all][0]!=tab[a][0])
            dp[a]=max(dp[a],dp[naj_in_all]+tab[a][0]-((tab[a][1]!=tab[naj_in_all][1])*k));
        dp[a]=max(dp[a],dp[naj_in_all2]+tab[a][0]-((tab[a][1]!=tab[naj_in_all2][1])*k));
        if(tab[naj[tab[a][1]][0]][0]!=tab[a][0])
            dp[a]=max(dp[a],dp[naj[tab[a][1]][0]]+tab[a][0]-((tab[a][1]!=tab[naj[tab[a][1]][0]][0])*k));
        dp[a]=max(dp[a],dp[naj[tab[a][1]][1]]+tab[a][0]-((tab[a][1]!=tab[naj[tab[a][1]][1]][1])*k));

        if(tab[a][0]!=tab[naj_in_all][0])
            naj_in_all2=naj_in_all;
        if(dp[a]>dp[naj_in_all])
            naj_in_all=a;
        if(tab[a][0]!=tab[naj[tab[a][1]][0]][0])
            naj[tab[a][1]][1]=naj[tab[a][1]][0];
        if(dp[a]>dp[naj[tab[a][1]][0]])
            naj[tab[a][1]][0]=a;
        odp=max(odp,dp[a]);
        //cout<<dp[a]<<"\n";
    }
    cout<<odp;
}