#include <bits/stdc++.h> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); long long n, c; cin >> n >> c; vector<pair<long long, long long>> b(n); for (auto &i : b) cin >> i.first >> i.second; const long long INF = -1e18; vector<long long> bp(500001, INF); long long ga = INF, res = 0; long long i = 0; while (i < n) { long long a = b[i].first; vector<pair<long long, long long>> g; //cout << j << '\n' << i << "chuj" <<'\n'; long long j = i; while (j < n and b[j].first == a) { long long w = b[j].second; long long cnd = max({0LL, bp[w], ga - c}); long long dp = a + cnd; g.emplace_back(w, dp); res = max(res, dp); j++; } for (auto &[w, dp] : g) { bp[w] = max(bp[w], dp); ga = max(ga, dp); } i = j; } cout << res; }
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 | #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0)->sync_with_stdio(0); long long n, c; cin >> n >> c; vector<pair<long long, long long>> b(n); for (auto &i : b) cin >> i.first >> i.second; const long long INF = -1e18; vector<long long> bp(500001, INF); long long ga = INF, res = 0; long long i = 0; while (i < n) { long long a = b[i].first; vector<pair<long long, long long>> g; //cout << j << '\n' << i << "chuj" <<'\n'; long long j = i; while (j < n and b[j].first == a) { long long w = b[j].second; long long cnd = max({0LL, bp[w], ga - c}); long long dp = a + cnd; g.emplace_back(w, dp); res = max(res, dp); j++; } for (auto &[w, dp] : g) { bp[w] = max(bp[w], dp); ga = max(ga, dp); } i = j; } cout << res; } |