#include <bits/stdc++.h> #define nl '\n' using namespace std; using ll = long long; const int MAXN = 5e5+1; unordered_map<ll, priority_queue<ll>> dp_color; priority_queue<ll> dp; vector<vector<ll>> by_height(MAXN); int main() { cin.tie(0)->sync_with_stdio(0); int n, c; cin>>n>>c; for(int i=0; i<n; i++){ ll a, w; cin>>a>>w; by_height[a].push_back(w); if(!dp_color[w].size()){ dp_color[w].push(0); } } dp.push(0); for(int i=MAXN-1; i>0; i--){ vector<pair<ll, ll>> dp_add; for(auto w: by_height[i]){ //cerr<<dp.top()-c<<' '<<dp_color[w].top()<<nl; dp_add.push_back({w, i+max(dp.top()-c, dp_color[w].top())}); } for(auto [w, res]: dp_add){ dp_color[w].push(res); dp.push(res); } } cout<<dp.top()<<nl; 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 | #include <bits/stdc++.h> #define nl '\n' using namespace std; using ll = long long; const int MAXN = 5e5+1; unordered_map<ll, priority_queue<ll>> dp_color; priority_queue<ll> dp; vector<vector<ll>> by_height(MAXN); int main() { cin.tie(0)->sync_with_stdio(0); int n, c; cin>>n>>c; for(int i=0; i<n; i++){ ll a, w; cin>>a>>w; by_height[a].push_back(w); if(!dp_color[w].size()){ dp_color[w].push(0); } } dp.push(0); for(int i=MAXN-1; i>0; i--){ vector<pair<ll, ll>> dp_add; for(auto w: by_height[i]){ //cerr<<dp.top()-c<<' '<<dp_color[w].top()<<nl; dp_add.push_back({w, i+max(dp.top()-c, dp_color[w].top())}); } for(auto [w, res]: dp_add){ dp_color[w].push(res); dp.push(res); } } cout<<dp.top()<<nl; return 0; } |