#include <bits/stdc++.h> using namespace std; #define int long long #define ii pair<int,int> #define iii tuple<int,int,int> #define fi first #define se second #define endl '\n' #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int n,k; ii arr[500005]; int dp[500005]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin>>n>>k; rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se; int MX=0; int l=1; while (l<=n){ vector<ii> tmp; do{ int val=arr[l].fi+max(dp[arr[l].se],MX-k); tmp.pub({val,arr[l].se}); l++; } while (l<=n && arr[l-1].fi==arr[l].fi); for (auto [a,b]:tmp){ dp[b]=max(dp[b],a); MX=max(MX,a); } } cout<<MX<<endl; }
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; #define int long long #define ii pair<int,int> #define iii tuple<int,int,int> #define fi first #define se second #define endl '\n' #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int n,k; ii arr[500005]; int dp[500005]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); cin>>n>>k; rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se; int MX=0; int l=1; while (l<=n){ vector<ii> tmp; do{ int val=arr[l].fi+max(dp[arr[l].se],MX-k); tmp.pub({val,arr[l].se}); l++; } while (l<=n && arr[l-1].fi==arr[l].fi); for (auto [a,b]:tmp){ dp[b]=max(dp[b],a); MX=max(MX,a); } } cout<<MX<<endl; } |