#include<iostream> #include<vector> #include<algorithm> #include<cmath> #include<set> #define ll long long using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int n,c; cin>>n>>c; vector<pair<int,int>>tab(n); int a,k,b; for(int i = 0;i<n;++i){ cin>>a>>k; tab[i]={a,k}; } vector<ll>best(500007,0); vector<ll>last_best(500007,0); ll best_h = 0; ll last_best_h = 0; int cur_a = 1000000; vector<pair<int,int>>usun; for(int i = n-1;i>=0;--i){ a=tab[i].first; b=tab[i].second; if(a==cur_a){ ll new_best = max(last_best_h+a-c,last_best[b]+a); if(best_h<new_best){ best_h=new_best; } if(best[b]<new_best){ best[b]=new_best; usun.push_back({b,new_best}); } } else{ //last_best = best; for(auto p : usun){ last_best[p.first]=p.second; } usun.clear(); last_best_h=best_h; cur_a=a; ll new_best = max(best_h+a-c,best[b]+a); if(best_h<new_best){ best_h=new_best; } if(best[b]<new_best){ best[b]=new_best; usun.push_back({b,new_best}); } } } cout<<best_h; 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 | #include<iostream> #include<vector> #include<algorithm> #include<cmath> #include<set> #define ll long long using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int n,c; cin>>n>>c; vector<pair<int,int>>tab(n); int a,k,b; for(int i = 0;i<n;++i){ cin>>a>>k; tab[i]={a,k}; } vector<ll>best(500007,0); vector<ll>last_best(500007,0); ll best_h = 0; ll last_best_h = 0; int cur_a = 1000000; vector<pair<int,int>>usun; for(int i = n-1;i>=0;--i){ a=tab[i].first; b=tab[i].second; if(a==cur_a){ ll new_best = max(last_best_h+a-c,last_best[b]+a); if(best_h<new_best){ best_h=new_best; } if(best[b]<new_best){ best[b]=new_best; usun.push_back({b,new_best}); } } else{ //last_best = best; for(auto p : usun){ last_best[p.first]=p.second; } usun.clear(); last_best_h=best_h; cur_a=a; ll new_best = max(best_h+a-c,best[b]+a); if(best_h<new_best){ best_h=new_best; } if(best[b]<new_best){ best[b]=new_best; usun.push_back({b,new_best}); } } } cout<<best_h; return 0; } |