Submission #718605

#	Time	Username	Problem	Language	Result	Execution time	Memory
718605		starplat	Salesman (IOI09_salesman)	C++14	17 / 100	3079 ms	12748 KiB

salesman

#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
int n,u,d,s,dp[500005][2];
pair<int,pair<int,int>> e[500005];
signed main(){
	cin>>n>>u>>d>>s;
	for (int i=1;i<=n;i++){
		cin>>e[i].f>>e[i].s.f>>e[i].s.s;
	}
	sort(e+1,e+1+n);
	int ans=0;
	for (int i=1;i<=n;){
		int pt=i;
		if (e[i].s.f>=s) dp[i][0]=e[i].s.s-(e[i].s.f-s)*d;
		else dp[i][0]=e[i].s.s-(s-e[i].s.f)*u;
		dp[i][1]=dp[i][0];	
		while (pt+1<=n && e[pt+1].f==e[i].f) {
			++pt;
			if (e[pt].s.f>=s) dp[pt][0]=e[pt].s.s-(e[pt].s.f-s)*d;
			else dp[pt][0]=e[pt].s.s-(s-e[pt].s.f)*u; 
			dp[pt][1]=dp[pt][1];
		}
		for (int j=i;j<=pt;j++){
			for (int k=1;k<j;k++){
				if (e[j].s.f>=e[k].s.f) dp[j][0]=max(dp[j][0],max(dp[k][0],dp[k][1])+e[j].s.s-(e[j].s.f-e[k].s.f)*d);
				else dp[j][0]=max(dp[j][0],max(dp[k][0],dp[k][1])+e[j].s.s-(e[k].s.f-e[j].s.f)*u);
			}
			if (e[j].s.f>=s) ans=max(ans,dp[j][0]-(e[j].s.f-s)*u);
			else ans=max(ans,dp[j][0]-(s-e[j].s.f)*d);
		}
		reverse(e+i,e+pt+1);
		reverse(dp+i,dp+pt+1);
		for (int j=i;j<=pt;j++){
			for (int k=1;k<j;k++){
				if (e[j].s.f>=e[k].s.f) dp[j][1]=max(dp[j][1],max(dp[k][0],dp[k][1])+e[j].s.s-(e[j].s.f-e[k].s.f)*d);
				else dp[j][1]=max(dp[j][1],max(dp[k][0],dp[k][1])+e[j].s.s-(e[k].s.f-e[j].s.f)*u);
			} 
			if (e[j].s.f>=s) ans=max(ans,dp[j][1]-(e[j].s.f-s)*u);
			else ans=max(ans,dp[j][1]-(s-e[j].s.f)*d);
		}
		reverse(e+i,e+pt+1);
		reverse(dp+i,dp+pt+1);
		//for (int j=i;j<=pt;j++) cout<<dp[j][0]<<" "<<dp[j][1]<<"\n"; 
		i=pt+1;
	}
	cout<<ans<<"\n";
}

• Subtask 1: 17 / 100