#include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second ll maxn=500009, mo; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll N, C; cin >> N >> C; vector<ll> dp(maxn); vector<pair<ll, ll>> vp; for (int i=0; i<N; i++){ int a, k; cin >> a >> k; vp.push_back({a, k}); } vp.push_back({-1000, maxn}); sort(vp.begin(), vp.end(), greater<pair<ll, ll>>()); bool rybka=true; vector<pair<ll, ll>> h; // cout << vp[0].f; for (int i=0; i<=N; i++){ int p=i; if (!i){ h.push_back({vp[0].s, vp[0].f}); continue; } if (vp[i].f!=vp[i-1].f){ for (auto j:h){ //cout << j.f << " " << j.s << endl; dp[j.f]=max(dp[j.f], j.s); mo=max(mo, dp[j.f]); } h.clear(); for (int l=1; l<5; l++){ // cout << l << " " << dp[l] << " " << mo << endl; } } ll z=dp[vp[p].s]+vp[i].f, c=mo-C+vp[i].f; z=max(z, c); if (z>dp[vp[p].s]){ h.push_back({vp[p].s, z}); } } cout << mo; 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 | #include <bits/stdc++.h> using namespace std; #define ll long long #define f first #define s second ll maxn=500009, mo; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll N, C; cin >> N >> C; vector<ll> dp(maxn); vector<pair<ll, ll>> vp; for (int i=0; i<N; i++){ int a, k; cin >> a >> k; vp.push_back({a, k}); } vp.push_back({-1000, maxn}); sort(vp.begin(), vp.end(), greater<pair<ll, ll>>()); bool rybka=true; vector<pair<ll, ll>> h; // cout << vp[0].f; for (int i=0; i<=N; i++){ int p=i; if (!i){ h.push_back({vp[0].s, vp[0].f}); continue; } if (vp[i].f!=vp[i-1].f){ for (auto j:h){ //cout << j.f << " " << j.s << endl; dp[j.f]=max(dp[j.f], j.s); mo=max(mo, dp[j.f]); } h.clear(); for (int l=1; l<5; l++){ // cout << l << " " << dp[l] << " " << mo << endl; } } ll z=dp[vp[p].s]+vp[i].f, c=mo-C+vp[i].f; z=max(z, c); if (z>dp[vp[p].s]){ h.push_back({vp[p].s, z}); } } cout << mo; return 0; } |