#include <bits/stdc++.h> using std::cin, std::cout; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; const char endl = '\n'; const int MAX_N = 500005; struct box { i64 height, pattern; }; int prev_with_pattern[MAX_N]{}; int next_same[MAX_N]{}; box boxes[MAX_N]; i64 best_pen[MAX_N]{}; i64 best_no_pen[MAX_N]{}; int next_larger[MAX_N]{}; int main() { std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n, penalty; cin >> n >> penalty; std::ranges::fill(prev_with_pattern, -1); std::ranges::fill(next_same, -1); for (int i = 0; i < n; i++) { int height, pattern; cin >> height >> pattern; boxes[i] = {height, pattern}; if (prev_with_pattern[pattern] != -1) { if (boxes[prev_with_pattern[pattern]].height == height) continue; // we cant take it anyways next_same[prev_with_pattern[pattern]] = i; } prev_with_pattern[pattern] = i; } { int prev_i = n; int prev = boxes[n - 1].height; for (int i = n - 1; i >= 0; i--) { if (boxes[i].height < prev) { prev_i = i + 1; } next_larger[i] = prev_i; prev = boxes[i].height; } } for (int i = 0; i < n; i++) { i64 next_score = std::max(best_pen[i] + boxes[i].height - penalty, best_no_pen[i] + boxes[i].height); if (next_same[i] != -1) { if (next_score > best_no_pen[next_same[i]]) best_no_pen[next_same[i]] = next_score; } if (next_score > best_pen[next_larger[i]]) best_pen[next_larger[i]] = next_score; if (best_pen[i] > best_pen[i + 1]) best_pen[i + 1] = best_pen[i]; } cout << std::max(best_pen[n], best_no_pen[n]); return 0; }
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 | #include <bits/stdc++.h> using std::cin, std::cout; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; const char endl = '\n'; const int MAX_N = 500005; struct box { i64 height, pattern; }; int prev_with_pattern[MAX_N]{}; int next_same[MAX_N]{}; box boxes[MAX_N]; i64 best_pen[MAX_N]{}; i64 best_no_pen[MAX_N]{}; int next_larger[MAX_N]{}; int main() { std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n, penalty; cin >> n >> penalty; std::ranges::fill(prev_with_pattern, -1); std::ranges::fill(next_same, -1); for (int i = 0; i < n; i++) { int height, pattern; cin >> height >> pattern; boxes[i] = {height, pattern}; if (prev_with_pattern[pattern] != -1) { if (boxes[prev_with_pattern[pattern]].height == height) continue; // we cant take it anyways next_same[prev_with_pattern[pattern]] = i; } prev_with_pattern[pattern] = i; } { int prev_i = n; int prev = boxes[n - 1].height; for (int i = n - 1; i >= 0; i--) { if (boxes[i].height < prev) { prev_i = i + 1; } next_larger[i] = prev_i; prev = boxes[i].height; } } for (int i = 0; i < n; i++) { i64 next_score = std::max(best_pen[i] + boxes[i].height - penalty, best_no_pen[i] + boxes[i].height); if (next_same[i] != -1) { if (next_score > best_no_pen[next_same[i]]) best_no_pen[next_same[i]] = next_score; } if (next_score > best_pen[next_larger[i]]) best_pen[next_larger[i]] = next_score; if (best_pen[i] > best_pen[i + 1]) best_pen[i + 1] = best_pen[i]; } cout << std::max(best_pen[n], best_no_pen[n]); return 0; } |