//Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; const int A = 5e5+7; void solve(){ int n, c; cin >> n >> c; //dp[a[i]][kolor] = max(dp[<a[i]][kolor rozny od tego] + a[i], dp[<a[i]][kolor] + a[i]-c) set<T>s; vector<vector<int>>tab(A); for (int i = 0; i<n; i++){ int a, w; cin >> a >> w; tab[a].emplace_back(w); } vector<int>dp(A, -1); for (int a = A-1; a>=1; a--){ vector<int>new_dp; for (auto w: tab[a]){ if (s.empty()) { new_dp.emplace_back(a); } else { auto it = s.rbegin(); auto [mx1, c1] = *it; int x = mx1 + a - (c1 != w ? c : 0); if (dp[w] != -1) { x = max(x, a + dp[w]); } debug(mx1, c1, x); if ((int)s.size() > 1){ it++; auto [mx2, c2] = *it; x = max(x, mx2 + a - (c2 != w ? c : 0)); } new_dp.emplace_back(x); } } for (int i = 0; i<(int)tab[a].size(); i++){ int w = tab[a][i]; if (dp[w] != -1){ s.erase({dp[w], w}); } dp[w] = max(dp[w], new_dp[i]); s.insert({dp[w], w}); } if (!tab[a].empty()){ debug(a, new_dp, s); } } assert(!s.empty()); cout << s.rbegin()->first << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); 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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | //Sylwia Sapkowska #include <bits/stdc++.h> #pragma GCC optimize("O3", "unroll-loops") using namespace std; void __print(int x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << "'" << x << "'";} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef LOCAL #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif #define int long long typedef pair<int, int> T; const int oo = 1e18, oo2 = 1e9+7, K = 30; const int mod = 998244353; const int A = 5e5+7; void solve(){ int n, c; cin >> n >> c; //dp[a[i]][kolor] = max(dp[<a[i]][kolor rozny od tego] + a[i], dp[<a[i]][kolor] + a[i]-c) set<T>s; vector<vector<int>>tab(A); for (int i = 0; i<n; i++){ int a, w; cin >> a >> w; tab[a].emplace_back(w); } vector<int>dp(A, -1); for (int a = A-1; a>=1; a--){ vector<int>new_dp; for (auto w: tab[a]){ if (s.empty()) { new_dp.emplace_back(a); } else { auto it = s.rbegin(); auto [mx1, c1] = *it; int x = mx1 + a - (c1 != w ? c : 0); if (dp[w] != -1) { x = max(x, a + dp[w]); } debug(mx1, c1, x); if ((int)s.size() > 1){ it++; auto [mx2, c2] = *it; x = max(x, mx2 + a - (c2 != w ? c : 0)); } new_dp.emplace_back(x); } } for (int i = 0; i<(int)tab[a].size(); i++){ int w = tab[a][i]; if (dp[w] != -1){ s.erase({dp[w], w}); } dp[w] = max(dp[w], new_dp[i]); s.insert({dp[w], w}); } if (!tab[a].empty()){ debug(a, new_dp, s); } } assert(!s.empty()); cout << s.rbegin()->first << "\n"; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; } |