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
// PA 2024 4C - Wieza
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	long long n, p, h, c, prevH, nextColor;
	long long bestCurr, bestPrev;
	vector<vector<long long>> colors;
	vector<bool> colorsUsed;
	vector<long long> heights;
	vector<long long> results;
	vector<long long> colorTrans;
	
	cin >> n;
	cin >> p;
	
	for (long long i = 0; i < 500000; ++i) {
		colorTrans.push_back(-1);
	}	
	
	prevH = -1;
	nextColor = 0;
	for (long long i = 0; i < n; ++i) {
		cin >> h;
		cin >> c;
		
		if (prevH != h) {
			heights.push_back(h);
			colors.push_back(vector<long long>());
		}
		
		if (colorTrans[c - 1] < 0) {
			colors[colors.size() - 1].push_back(nextColor);
			colorTrans[c - 1] = nextColor;
			++nextColor;
		} else {
			colors[colors.size() - 1].push_back(colorTrans[c - 1]);
		}	
		prevH = h;	
	}
	
	reverse(heights.begin(), heights.end());
	reverse(colors.begin(), colors.end());
	
	for (long long i = 0; i < n; ++i) {
		results.push_back(0);
		colorsUsed.push_back(false);
	}
	bestCurr = 0;
	
	/*for (int i = 0; i < colors.size(); ++i) {
		cout << heights[i] << ": ";
		for (int j = 0; j < colors[i].size(); ++j) {
			cout << colors[i][j] << " ";
		} cout << endl;
	}
	cout << endl << endl;*/
	
	for (unsigned long long i = 0; i < heights.size(); ++i) {
		bestPrev = bestCurr;
		for (unsigned long long j = 0; j < colors[i].size(); ++j) {
			if (colorsUsed[colors[i][j]]) {
				continue;
			}
			colorsUsed[colors[i][j]] = true;
			//cout << results[colors[i][j]] << "-" << heights[i] << "-" << bestPrev << "-" << heights[i] << "-" << p << endl;
			results[colors[i][j]] = max(results[colors[i][j]] + heights[i], bestPrev + heights[i] - p);
			if (bestCurr < results[colors[i][j]]) {
				bestCurr = results[colors[i][j]];
			}
		}
		for (unsigned long long j = 0; j < colors[i].size(); ++j) {
			colorsUsed[colors[i][j]] = false;
		}
		
		/*cout << i << ": ";
		for (int j = 0; j < n; ++j) {
			cout << results[j] << " ";
		} cout << endl;*/
	}
	
	cout << bestCurr;	
	
	return 0;
}