#include <iostream> using namespace std; int tab[500'007][2]; int dp[500'007]; int naj[500'007][2]; main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k, odp=0, naj_in_all=0, naj_in_all2=0; cin>>n>>k; for(int a=1; a<=n; a++) cin>>tab[a][0]>>tab[a][1]; for(int a=1; a<=n; a++) { dp[a]=tab[a][0]; if(tab[naj_in_all][0]!=tab[a][0]) dp[a]=max(dp[a],dp[naj_in_all]+tab[a][0]-((tab[a][1]!=tab[naj_in_all][1])*k)); dp[a]=max(dp[a],dp[naj_in_all2]+tab[a][0]-((tab[a][1]!=tab[naj_in_all2][1])*k)); if(tab[naj[tab[a][1]][0]][0]!=tab[a][0]) dp[a]=max(dp[a],dp[naj[tab[a][1]][0]]+tab[a][0]-((tab[a][1]!=tab[naj[tab[a][1]][0]][0])*k)); dp[a]=max(dp[a],dp[naj[tab[a][1]][1]]+tab[a][0]-((tab[a][1]!=tab[naj[tab[a][1]][1]][1])*k)); if(tab[a][0]!=tab[naj_in_all][0]) naj_in_all2=naj_in_all; if(dp[a]>dp[naj_in_all]) naj_in_all=a; if(tab[a][0]!=tab[naj[tab[a][1]][0]][0]) naj[tab[a][1]][1]=naj[tab[a][1]][0]; if(dp[a]>dp[naj[tab[a][1]][0]]) naj[tab[a][1]][0]=a; odp=max(odp,dp[a]); //cout<<dp[a]<<"\n"; } cout<<odp; }
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 | #include <iostream> using namespace std; int tab[500'007][2]; int dp[500'007]; int naj[500'007][2]; main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k, odp=0, naj_in_all=0, naj_in_all2=0; cin>>n>>k; for(int a=1; a<=n; a++) cin>>tab[a][0]>>tab[a][1]; for(int a=1; a<=n; a++) { dp[a]=tab[a][0]; if(tab[naj_in_all][0]!=tab[a][0]) dp[a]=max(dp[a],dp[naj_in_all]+tab[a][0]-((tab[a][1]!=tab[naj_in_all][1])*k)); dp[a]=max(dp[a],dp[naj_in_all2]+tab[a][0]-((tab[a][1]!=tab[naj_in_all2][1])*k)); if(tab[naj[tab[a][1]][0]][0]!=tab[a][0]) dp[a]=max(dp[a],dp[naj[tab[a][1]][0]]+tab[a][0]-((tab[a][1]!=tab[naj[tab[a][1]][0]][0])*k)); dp[a]=max(dp[a],dp[naj[tab[a][1]][1]]+tab[a][0]-((tab[a][1]!=tab[naj[tab[a][1]][1]][1])*k)); if(tab[a][0]!=tab[naj_in_all][0]) naj_in_all2=naj_in_all; if(dp[a]>dp[naj_in_all]) naj_in_all=a; if(tab[a][0]!=tab[naj[tab[a][1]][0]][0]) naj[tab[a][1]][1]=naj[tab[a][1]][0]; if(dp[a]>dp[naj[tab[a][1]][0]]) naj[tab[a][1]][0]=a; odp=max(odp,dp[a]); //cout<<dp[a]<<"\n"; } cout<<odp; } |