#include <bits/stdc++.h> using namespace std; #define FOR(i, b) for (int i = 0; i < b; ++i) #define sz(s) (int)s.size() #define all(s) s.begin(), s.end() #define mp make_pair #define pb push_back #define f first #define s second const int N = 500004; unordered_map<int, int> cnt; long long dp_dowolny[N]; long long dp_ten_konkretnie[N]; template <typename T> T& setmax(T& a, T b) { return a = max(a, b); } void solve() { int n, c; cin >> n >> c; vector<pair<int, int>> tab(n); for (auto &i : tab) cin >> i.f >> i.s; reverse(all(tab)); map<int, pair<int, int> > ostatni; auto dodaj = [&](int wzorek, int i) { auto & [ost, przedost] = ostatni[wzorek]; if (ost == -1 or tab[ost].f == tab[i].f) { ost = i; } else { przedost = ost; ost = i; } }; int ostatni_inny_rozmiar = -1; for (auto [wys, wzorek]: tab) { ostatni[wzorek] = {-1, -1}; } for (int i = 0; i < n; i++) { const auto & [wys, wzorek] = tab[i]; if (i > 0 and wys != tab[i - 1].f) { ostatni_inny_rozmiar = i - 1; } dp_ten_konkretnie[i] = wys; if (ostatni_inny_rozmiar != -1) { setmax(dp_ten_konkretnie[i], dp_dowolny[ostatni_inny_rozmiar] + wys - c); } auto [ost, przedost] = ostatni[wzorek]; if (ost != -1 and tab[ost].f > wys) { setmax(dp_ten_konkretnie[i], dp_ten_konkretnie[ost] + wys); } else if (przedost != -1) { setmax(dp_ten_konkretnie[i], dp_ten_konkretnie[przedost] + wys); } setmax(dp_dowolny[i], dp_ten_konkretnie[i]); if (i > 0) { setmax(dp_dowolny[i], dp_dowolny[i - 1]); } // update'y dodaj(wzorek, i); // cout << "DP " << wys << ' ' << wzorek << ' ' << dp_ten_konkretnie[i] << ' ' << dp_dowolny[i] << '\n'; } cout << dp_dowolny[n - 1] << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); }
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 91 92 93 94 95 96 97 98 99 100 | #include <bits/stdc++.h> using namespace std; #define FOR(i, b) for (int i = 0; i < b; ++i) #define sz(s) (int)s.size() #define all(s) s.begin(), s.end() #define mp make_pair #define pb push_back #define f first #define s second const int N = 500004; unordered_map<int, int> cnt; long long dp_dowolny[N]; long long dp_ten_konkretnie[N]; template <typename T> T& setmax(T& a, T b) { return a = max(a, b); } void solve() { int n, c; cin >> n >> c; vector<pair<int, int>> tab(n); for (auto &i : tab) cin >> i.f >> i.s; reverse(all(tab)); map<int, pair<int, int> > ostatni; auto dodaj = [&](int wzorek, int i) { auto & [ost, przedost] = ostatni[wzorek]; if (ost == -1 or tab[ost].f == tab[i].f) { ost = i; } else { przedost = ost; ost = i; } }; int ostatni_inny_rozmiar = -1; for (auto [wys, wzorek]: tab) { ostatni[wzorek] = {-1, -1}; } for (int i = 0; i < n; i++) { const auto & [wys, wzorek] = tab[i]; if (i > 0 and wys != tab[i - 1].f) { ostatni_inny_rozmiar = i - 1; } dp_ten_konkretnie[i] = wys; if (ostatni_inny_rozmiar != -1) { setmax(dp_ten_konkretnie[i], dp_dowolny[ostatni_inny_rozmiar] + wys - c); } auto [ost, przedost] = ostatni[wzorek]; if (ost != -1 and tab[ost].f > wys) { setmax(dp_ten_konkretnie[i], dp_ten_konkretnie[ost] + wys); } else if (przedost != -1) { setmax(dp_ten_konkretnie[i], dp_ten_konkretnie[przedost] + wys); } setmax(dp_dowolny[i], dp_ten_konkretnie[i]); if (i > 0) { setmax(dp_dowolny[i], dp_dowolny[i - 1]); } // update'y dodaj(wzorek, i); // cout << "DP " << wys << ' ' << wzorek << ' ' << dp_ten_konkretnie[i] << ' ' << dp_dowolny[i] << '\n'; } cout << dp_dowolny[n - 1] << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); } |