#include <iostream> #include <vector> #include <algorithm> #include <tuple> using namespace std; typedef pair<int,int> pii; const int BASE = 1<<19; vector<pii> blocks; int height[2*BASE] {}; void set(int p, int val){ p += BASE; height[p] = val; while(p > 0){ p >>= 1; height[p] = max(height[2*p], height[2*p+1]); } } int query(int p, int q){ int ret = 0; p += BASE -1; q += BASE +1; while(p>>1 != q>>1){ if(!(p&1)){ ret = max(ret, height[p+1]); } if(q&1){ ret = max(ret, height[q-1]); } p >>= 1; q >>= 1; } return ret; } bool cmp(pii l, pii r){ return l.first > r.first; } int main(){ int n, c; cin >> n >> c; for(int i = 0; i < n; i++){ int a, w; cin >> a >> w; blocks.push_back({a,w}); } sort(blocks.begin(),blocks.end(),cmp); for(int i = 0; i < blocks.size(); i++){ int a, w; tie(a, w) = blocks[i]; int same = query(w,w); int diff = max(query(0,w-1),query(w+1,BASE)); set(w, max(same + a, diff + a - c)); // cout << a << " " << w << ": " << endl; // cout << same << " " << diff << endl; // cout << same + a << " " << diff + a - c << "; max " << max(same + a, diff + a - c) << endl; // cout << query(0,BASE) << endl << endl; } cout << query(0,BASE); 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 75 | #include <iostream> #include <vector> #include <algorithm> #include <tuple> using namespace std; typedef pair<int,int> pii; const int BASE = 1<<19; vector<pii> blocks; int height[2*BASE] {}; void set(int p, int val){ p += BASE; height[p] = val; while(p > 0){ p >>= 1; height[p] = max(height[2*p], height[2*p+1]); } } int query(int p, int q){ int ret = 0; p += BASE -1; q += BASE +1; while(p>>1 != q>>1){ if(!(p&1)){ ret = max(ret, height[p+1]); } if(q&1){ ret = max(ret, height[q-1]); } p >>= 1; q >>= 1; } return ret; } bool cmp(pii l, pii r){ return l.first > r.first; } int main(){ int n, c; cin >> n >> c; for(int i = 0; i < n; i++){ int a, w; cin >> a >> w; blocks.push_back({a,w}); } sort(blocks.begin(),blocks.end(),cmp); for(int i = 0; i < blocks.size(); i++){ int a, w; tie(a, w) = blocks[i]; int same = query(w,w); int diff = max(query(0,w-1),query(w+1,BASE)); set(w, max(same + a, diff + a - c)); // cout << a << " " << w << ": " << endl; // cout << same << " " << diff << endl; // cout << same + a << " " << diff + a - c << "; max " << max(same + a, diff + a - c) << endl; // cout << query(0,BASE) << endl << endl; } cout << query(0,BASE); return 0; } |