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
#include <iostream>
#include <vector>
#include <algorithm>

long long calculateBestTowerOnTheFly() {
    long long n, penalty;
    std::cin >> n >> penalty;
    
    long long bestTower = 0;
    long long bestTowerNValue = 0;
    long long smallerTower = 0;
    long long bestSmallerNValue = 0;
    std::vector<long long> patterns(500001, 0);
    std::vector<long long> heights(500001, 0);

    for (int i = 0; i < n; i++) {
        long long value, pattern;
        std::cin >> value >> pattern;
        if (heights[pattern] == value) {
            continue;
        }
        long long candidate = patterns[pattern] + value;
        long long secondCandidate = bestTower + value - penalty;
        if (bestTowerNValue == value) {
            secondCandidate = smallerTower + value - penalty;
        }

        if(std::max(candidate, secondCandidate) > bestTower) {
            if(value > bestTowerNValue) {
                smallerTower = bestTower;
                bestSmallerNValue = bestTowerNValue;
            }
            bestTowerNValue = value;
            bestTower = std::max(bestTower, std::max(candidate, secondCandidate));
        }
		if (value > heights[pattern]) {
            patterns[pattern] = std::max(candidate, secondCandidate);
		}    
        heights[pattern] = value;
    }
    
    return bestTower;
}

int main() {
    long long result = calculateBestTowerOnTheFly();
    std::cout << result << std::endl;
    return 0;
}