#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define imie(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const int mod=1e9+7; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const ll INF = -1e18; struct T { int a; int w; }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, c; cin >> n >> c; vector<T> v(n); for(int i = 0; i < n; i++){ cin >> v[i].a >> v[i].w; } int idx = n - 1; vector<ll> best(500001, INF); ll ans2 = INF, ans = 0; while(idx >= 0){ int siz = v[idx].a; vector<ll> dp; vector<int> g; while(idx >= 0 && v[idx].a == siz){ int w = v[idx].w; ll cs = best[w]; ll cd = (ans2 == INF ? INF : ans2 - c); ll kand = max({0LL, cs, cd}); dp.push_back(siz + kand); g.push_back(w); ans = max(ans, siz + kand); idx--; } for(int i = 0; i < dp.size(); i++){ int p = g[i]; best[p] = max(best[p], dp[i]); ans2 = max(ans2, dp[i]); } } cout << ans << "\n"; 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 | #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define imie(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const int mod=1e9+7; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const ll INF = -1e18; struct T { int a; int w; }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, c; cin >> n >> c; vector<T> v(n); for(int i = 0; i < n; i++){ cin >> v[i].a >> v[i].w; } int idx = n - 1; vector<ll> best(500001, INF); ll ans2 = INF, ans = 0; while(idx >= 0){ int siz = v[idx].a; vector<ll> dp; vector<int> g; while(idx >= 0 && v[idx].a == siz){ int w = v[idx].w; ll cs = best[w]; ll cd = (ans2 == INF ? INF : ans2 - c); ll kand = max({0LL, cs, cd}); dp.push_back(siz + kand); g.push_back(w); ans = max(ans, siz + kand); idx--; } for(int i = 0; i < dp.size(); i++){ int p = g[i]; best[p] = max(best[p], dp[i]); ans2 = max(ans2, dp[i]); } } cout << ans << "\n"; return 0; } |