#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; signed main() { cin.tie(0) -> sync_with_stdio(0); int n, C; cin >> n >> C; map<int, int> dprn; int bestall = 0, finalment = 0; vector<pii> v(n); vector<int> atrdp(n + 1); for(auto &[a, w] : v) cin >> a >> w; v.emplace_back(0, -1); int lst = -1; for(int i = 0; i <= n; i++) { if(v[i].first != lst) { for(int j = i - 1; j >= 0 && v[j].first == v[i - 1].first; j--) { dprn[v[j].second] = max(dprn[v[j].second], atrdp[j]); bestall = max(bestall, atrdp[j] - C); } } lst = v[i].first; atrdp[i] = v[i].first + max(bestall, dprn[v[i].second]); finalment = max(finalment, atrdp[i]); } cout << finalment << '\n'; } /** Binecuvanteaza Doamne Ukraina. -- */
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> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; signed main() { cin.tie(0) -> sync_with_stdio(0); int n, C; cin >> n >> C; map<int, int> dprn; int bestall = 0, finalment = 0; vector<pii> v(n); vector<int> atrdp(n + 1); for(auto &[a, w] : v) cin >> a >> w; v.emplace_back(0, -1); int lst = -1; for(int i = 0; i <= n; i++) { if(v[i].first != lst) { for(int j = i - 1; j >= 0 && v[j].first == v[i - 1].first; j--) { dprn[v[j].second] = max(dprn[v[j].second], atrdp[j]); bestall = max(bestall, atrdp[j] - C); } } lst = v[i].first; atrdp[i] = v[i].first + max(bestall, dprn[v[i].second]); finalment = max(finalment, atrdp[i]); } cout << finalment << '\n'; } /** Binecuvanteaza Doamne Ukraina. -- */ |