Submission #1156664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156664		Doncho_Bonboncho	Salesman (IOI09_salesman)	C++20	19 / 100	3096 ms	19992 KiB

salesman

#include <algorithm>
#include <bits/stdc++.h>
#include <random>
#include <utility>
#include <vector>
using namespace std;

#ifndef LOCAL
#define cerr if(false) cerr
#endif

#define out( x ) #x << " = " << x << "  "
#define endl "\n"

template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }

typedef long long ll;
#define int ll
const ll mod = 1e9 +7;
const ll inf = 1e18;
const int MAX_N = 1e6 + 42;

std::vector< std::pair< int, std::pair< int, int > > > v;
signed main(){
#ifndef LOCAL
	std::ios_base::sync_with_stdio( false ); std::cin.tie( NULL ); std::cout.tie( NULL );
#endif

	int n, U, D, L;
	std::cin >> n >> U >> D >> L;

	for( int i=1 ; i <= n ; i++ ){
		int t, l, c;
		std::cin >> t >> l >> c;
		v.push_back({ t, { l, c }});
	}
	v.push_back({ -1, { L, 0 } });
	v.push_back({ mod, { L, 0 } });

	std::sort( v.begin(), v.end() );

	for( int i=0 ; i < v.size() ; i++ ){
		cerr << out( i ) << out( v[i].first ) << out( v[i].second.first ) << out( v[i].second.second ) << endl;
	}
	cerr << endl;
	/*
	int ind = 1;
	while( ind < n and v[ind].first == v[0].first ){
		dp[ind ++] = 0;
	}
	cerr << out( ind ) << endl;
	*/

	std::vector< ll > dp( MAX_N, -inf );
	dp[0] = 0;
	for( int i=1 ; i < v.size() ; i++ ){
		for( int j=0 ; j < i ; j ++ ){
			ll cost;
			ll dist = (ll)v[j].second.first - v[i].second.first;
			if( dist > 0 ) cost = (ll)dist * U;
			else cost = -(ll)dist * D;
			ll A = dp[j] - cost + v[i].second.second;
			cerr << out( j ) << out( A ) << endl;

			chkmax( dp[i], A );
		}
		cerr << out( i ) << out( dp[i] ) << endl << endl;
	}

	std::cout << dp[ v.size() -1 ] << endl;

	return 0;
}

• Subtask 1: 19 / 100