#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; typedef long long int lli; struct tower { lli a; lli score; }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); lli n, c, a, w; cin >> n >> c; tower hi1, hi2; hi1.a = 0; hi1.score = 0; hi2 = hi1; vector<tower> patterns(500000 + 1, hi1); while ( n-- ) { cin >> a >> w; lli score = 0; score = patterns[w].score; if (patterns[w].a < a) score += a; if ( hi1.a < a ) { score = max(score, a + hi1.score - c); if ( score > hi1.score ) { hi2 = hi1; hi1.a = a; hi1.score = score; } } else { score = max(score, a + hi2.score - c); if ( score > hi1.score ) { hi1.score = score; hi1.a = a; } } patterns[w].a = a; patterns[w].score = score; } cout << hi1.score << "\n"; }
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 | #include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; typedef long long int lli; struct tower { lli a; lli score; }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); lli n, c, a, w; cin >> n >> c; tower hi1, hi2; hi1.a = 0; hi1.score = 0; hi2 = hi1; vector<tower> patterns(500000 + 1, hi1); while ( n-- ) { cin >> a >> w; lli score = 0; score = patterns[w].score; if (patterns[w].a < a) score += a; if ( hi1.a < a ) { score = max(score, a + hi1.score - c); if ( score > hi1.score ) { hi2 = hi1; hi1.a = a; hi1.score = score; } } else { score = max(score, a + hi2.score - c); if ( score > hi1.score ) { hi1.score = score; hi1.a = a; } } patterns[w].a = a; patterns[w].score = score; } cout << hi1.score << "\n"; } |