Submission #655380

#	Time	Username	Problem	Language	Result	Execution time	Memory
655380		denniskim	Salesman (IOI09_salesman)	C++17	6 / 100	3093 ms	16136 KiB

salesman

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define sp << " "
#define en << "\n"

struct GUJO
{
	ll T, L, M;
};

bool sort1(GUJO X, GUJO Y)
{
	if(X.T != Y.T)
		return X.T < Y.T;
	
	return X.L < Y.L;
}

bool sort2(GUJO X, GUJO Y)
{
	if(X.T != Y.T)
		return X.T < Y.T;
	
	return X.L > Y.L;
}

ll n, U, D, S;
GUJO a[500010];
ll dp[500010];
ll ans;

ll solve(void)
{
	for(ll i = 0 ; i <= n + 1 ; i++)
		dp[i] = 0;
	
	for(ll i = 1 ; i <= n + 1 ; i++)
	{
		for(ll j = 0 ; j < i ; j++)
		{
			if(a[i].L < a[j].L)
				dp[i] = max(dp[i], dp[j] - (a[j].L - a[i].L) * U + a[i].M);
			else
				dp[i] = max(dp[i], dp[j] - (a[i].L - a[j].L) * D + a[i].M);
		}
	}
	
	return dp[n + 1];
}

int main(void)
{
	fastio
	
	cin >> n >> U >> D >> S;
	
	a[0].T = -1;
	a[0].L = S;
	a[0].M = 0;
	
	for(ll i = 1 ; i <= n ; i++)
		cin >> a[i].T >> a[i].L >> a[i].M;
	
	sort(a + 1, a + 1 + n, sort1);
	
	a[n + 1].T = -1;
	a[n + 1].L = S;
	a[n + 1].M = 0;
	
	ll ans = solve();
	
	sort(a + 1, a + 1 + n, sort2);
	
	cout << max(ans, solve());
	return 0;
}

• Subtask 1: 6 / 100