Submission #705776

#	Time	Username	Problem	Language	Result	Execution time	Memory
705776		starplat	Salesman (IOI09_salesman)	C++14	19 / 100	3079 ms	21348 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];
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;i++){
		if (e[i].s.f>=s) dp[i]=e[i].s.s-(e[i].s.f-s)*d;
		else dp[i]=e[i].s.s-(s-e[i].s.f)*u; 
		for (int j=1;j<i;j++){
			if (e[i].s.f>=e[j].s.f) dp[i]=max(dp[i],dp[j]+e[i].s.s-(e[i].s.f-e[j].s.f)*d);
			else dp[i]=max(dp[i],dp[j]+e[i].s.s-(e[j].s.f-e[i].s.f)*u);
		}
		if (e[i].s.f>=s) ans=max(ans,dp[i]-(e[i].s.f-s)*u);
		else ans=max(ans,dp[i]-(s-e[i].s.f)*d);
	}
	cout<<ans<<"\n";
}

• Subtask 1: 19 / 100