#include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <unordered_map> #include <unordered_set> #include <queue> #include <deque> #include <tuple> #include <bitset> using namespace std; #define pb push_back #define mp make_pair #define st first #define nd second #define x first #define y second typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; ll best_color[500001]; ll best_all=0; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, c; cin >> n >> c; map<ll, set<ll>> boxes; for(int i=0; i<n; i++){ ll a, w; cin >> a >> w; boxes[a].insert(w); } ll ans = 0; for (auto& a: boxes) { vector<pll> size_dp; for(auto w: a.nd){ ll dp = a.st + max(0ll, max(best_all - c, best_color[w])); ans = max(ans, dp); size_dp.pb(mp(dp, w)); } for(auto dp: size_dp){ best_all = max(best_all, dp.st); best_color[dp.nd] = max(best_color[dp.nd], dp.st); } } cout << ans; 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 | #include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <unordered_map> #include <unordered_set> #include <queue> #include <deque> #include <tuple> #include <bitset> using namespace std; #define pb push_back #define mp make_pair #define st first #define nd second #define x first #define y second typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vll; ll best_color[500001]; ll best_all=0; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, c; cin >> n >> c; map<ll, set<ll>> boxes; for(int i=0; i<n; i++){ ll a, w; cin >> a >> w; boxes[a].insert(w); } ll ans = 0; for (auto& a: boxes) { vector<pll> size_dp; for(auto w: a.nd){ ll dp = a.st + max(0ll, max(best_all - c, best_color[w])); ans = max(ans, dp); size_dp.pb(mp(dp, w)); } for(auto dp: size_dp){ best_all = max(best_all, dp.st); best_color[dp.nd] = max(best_color[dp.nd], dp.st); } } cout << ans; return 0; } |