#include <bits/stdc++.h> using namespace std; #define all(x) begin(x),end(x) #define pb push_back #define st first #define nd second typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int INF = 2e9; const ll LLINF = 2e18; struct block { ll a; int w; }; void solve() { int n,c; cin>>n>>c; vector<block> v(n); for(auto& b:v) cin>>b.a>>b.w; reverse(all(v)); vector<ll> dp(n); unordered_map<int,ll> last_dp; vll use(n); for(auto b:v) last_dp[b.w] = 0; dp[0] = v[0].a; use[0] = v[0].a; last_dp[v[0].w] = dp[0]; int i=1; while(i<n && v[i].a==v[i-1].a) { dp[i] = v[i].a; use[i] = v[i].a; last_dp[v[i].w] = max(last_dp[v[i].w], v[i].a); ++i; } while(i<n) { int j=i; while(j<n && v[j].a==v[i].a) { use[j] = max(dp[i-1]+v[j].a-c, last_dp[v[j].w]+v[j].a); dp[j] = max(dp[i-1], use[j]); ++j; } while(i<j) { last_dp[v[i].w] = max(last_dp[v[i].w], use[i]); dp[i] = max(dp[i], dp[i-1]); ++i; } } cout<<dp[n-1]<<"\n"; /*for(auto x:use) cout<<x<<" "; cout<<"\n"; for(auto x:dp) cout<<x<<" "; cout<<"\n";*/ } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int z=1; //cin>>z; while(z--) 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 | #include <bits/stdc++.h> using namespace std; #define all(x) begin(x),end(x) #define pb push_back #define st first #define nd second typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int INF = 2e9; const ll LLINF = 2e18; struct block { ll a; int w; }; void solve() { int n,c; cin>>n>>c; vector<block> v(n); for(auto& b:v) cin>>b.a>>b.w; reverse(all(v)); vector<ll> dp(n); unordered_map<int,ll> last_dp; vll use(n); for(auto b:v) last_dp[b.w] = 0; dp[0] = v[0].a; use[0] = v[0].a; last_dp[v[0].w] = dp[0]; int i=1; while(i<n && v[i].a==v[i-1].a) { dp[i] = v[i].a; use[i] = v[i].a; last_dp[v[i].w] = max(last_dp[v[i].w], v[i].a); ++i; } while(i<n) { int j=i; while(j<n && v[j].a==v[i].a) { use[j] = max(dp[i-1]+v[j].a-c, last_dp[v[j].w]+v[j].a); dp[j] = max(dp[i-1], use[j]); ++j; } while(i<j) { last_dp[v[i].w] = max(last_dp[v[i].w], use[i]); dp[i] = max(dp[i], dp[i-1]); ++i; } } cout<<dp[n-1]<<"\n"; /*for(auto x:use) cout<<x<<" "; cout<<"\n"; for(auto x:dp) cout<<x<<" "; cout<<"\n";*/ } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int z=1; //cin>>z; while(z--) solve(); return 0; } |