#include <bits/stdc++.h> using namespace std; #define fwd(i, a, n) for (int i = (a); i < (n); i++) #define rep(i, n) fwd(i, 0, n) #define all(X) X.begin(), X.end() #define sz(X) int(size(X)) #define pb push_back #define eb emplace_back #define st first #define nd second using pii = pair<int, int>; using vi = vector<int>; using ll = long long; using ld = long double; #ifdef LOC auto SS = signal(6, [](int) { *(int *)0 = 0; }); #define DTP(x, y) auto operator << (auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; } DTP(o << a.st << ", " << a.nd, a.nd); DTP(for (auto i : a) o << i << ", ", all(a)); void dump(auto... x) { (( cerr << x << ", " ), ...) << '\n'; } #define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x) #else #define deb(...) 0 #endif #define S 500007 ll dp[S]; ll pref[S]; vector<int> V[S]; int H[S]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(10); int n,c; cin >> n >> c; int l = 0; for(int i = 1; i <= n; i++) { ll a,w; cin >> a >> w; H[i] = a; while(l + 1 < i && H[l+1] < H[i]) { l++; } dp[i] = a; dp[i] = max(dp[i], pref[l] + a - c); if(!V[w].empty()) { int v = V[w].back(); if(H[v] == H[i]) { dp[i] = max(dp[i], dp[v]); } else { dp[i] = max(dp[i], dp[v] + a); } } V[w].pb(i); pref[i] = max(pref[i-1], dp[i]); } cout << pref[n] << "\n"; }
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 | #include <bits/stdc++.h> using namespace std; #define fwd(i, a, n) for (int i = (a); i < (n); i++) #define rep(i, n) fwd(i, 0, n) #define all(X) X.begin(), X.end() #define sz(X) int(size(X)) #define pb push_back #define eb emplace_back #define st first #define nd second using pii = pair<int, int>; using vi = vector<int>; using ll = long long; using ld = long double; #ifdef LOC auto SS = signal(6, [](int) { *(int *)0 = 0; }); #define DTP(x, y) auto operator << (auto &o, auto a) -> decltype(y, o) { o << "("; x; return o << ")"; } DTP(o << a.st << ", " << a.nd, a.nd); DTP(for (auto i : a) o << i << ", ", all(a)); void dump(auto... x) { (( cerr << x << ", " ), ...) << '\n'; } #define deb(x...) cerr << setw(4) << __LINE__ << ":[" #x "]: ", dump(x) #else #define deb(...) 0 #endif #define S 500007 ll dp[S]; ll pref[S]; vector<int> V[S]; int H[S]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cout << fixed << setprecision(10); int n,c; cin >> n >> c; int l = 0; for(int i = 1; i <= n; i++) { ll a,w; cin >> a >> w; H[i] = a; while(l + 1 < i && H[l+1] < H[i]) { l++; } dp[i] = a; dp[i] = max(dp[i], pref[l] + a - c); if(!V[w].empty()) { int v = V[w].back(); if(H[v] == H[i]) { dp[i] = max(dp[i], dp[v]); } else { dp[i] = max(dp[i], dp[v] + a); } } V[w].pb(i); pref[i] = max(pref[i-1], dp[i]); } cout << pref[n] << "\n"; } |