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
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	long long int c;
	cin>>n>>c;
	vector<long long int>v(500007,0);
	long long int a;
	int w;
	cin>>a>>w;
	long long int mo=0;
	long long int ma=a;
	queue<pair<int,long long int>>q;
	q.push({w,a});
	for(int i=1; i<n; i++)
	{
		int pop=a;
		cin>>a>>w;
		if(a!=pop)
		{
			while(!q.empty())
			{
				auto x=q.front();
				q.pop();
				v[x.first]=max(v[x.first],x.second);
			}
			mo=ma;
		}
		q.push({w,max(v[w]+a,mo+a-c)});
		ma=max(ma,max(v[w]+a,mo+a-c));
	}
	cout<<ma<<"\n";
}