#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "debug.hpp" #else #define debug(...) (void)0 #endif namespace R = ranges; namespace V = views; auto ra(auto x, auto y) { return R::iota_view(x, y); } auto rae(auto x, auto y) { return ra(x, y + 1); } using i64 = int64_t; void solve() { int n, c; cin >> n >> c; vector<array<int, 2>> v(n + 1); for (auto i : rae(1, n)) { auto &[ai, wi] = v[i]; cin >> ai >> wi; } debug(v); vector<i64> dp(n + 1); map<int, i64> czokapik; i64 guwno = 0; for (auto i : rae(1, n)) { auto [ai, wi] = v[i]; dp[i] = max(guwno + ai - c, czokapik[wi] + ai); if(i != n and v[i + 1][0] != ai) { int j = i; while (v[j][0] == v[i][0]) { czokapik[v[j][1]] = max(czokapik[v[j][1]], dp[j]); guwno = max(guwno, dp[j]); j -= 1; } } } debug(czokapik, dp); cout << R::max(dp) << '\n'; } int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); int t = 1; // cin >> t; for (auto tc_n : ra(0, t)) { debug(tc_n); solve(); cout.flush(); } }
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 | #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "debug.hpp" #else #define debug(...) (void)0 #endif namespace R = ranges; namespace V = views; auto ra(auto x, auto y) { return R::iota_view(x, y); } auto rae(auto x, auto y) { return ra(x, y + 1); } using i64 = int64_t; void solve() { int n, c; cin >> n >> c; vector<array<int, 2>> v(n + 1); for (auto i : rae(1, n)) { auto &[ai, wi] = v[i]; cin >> ai >> wi; } debug(v); vector<i64> dp(n + 1); map<int, i64> czokapik; i64 guwno = 0; for (auto i : rae(1, n)) { auto [ai, wi] = v[i]; dp[i] = max(guwno + ai - c, czokapik[wi] + ai); if(i != n and v[i + 1][0] != ai) { int j = i; while (v[j][0] == v[i][0]) { czokapik[v[j][1]] = max(czokapik[v[j][1]], dp[j]); guwno = max(guwno, dp[j]); j -= 1; } } } debug(czokapik, dp); cout << R::max(dp) << '\n'; } int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); int t = 1; // cin >> t; for (auto tc_n : ra(0, t)) { debug(tc_n); solve(); cout.flush(); } } |