Submission #1156694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156694		Doncho_Bonboncho	Salesman (IOI09_salesman)	C++20	62 / 100	502 ms	51224 KiB

salesman

#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
#include <random>
#include <utility>
#include <variant>
#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 = 1e17;
const int MAX_N = 5e5 + 42;


const ll neutr = -inf;

struct SegmentTree{

	std::vector< ll > tree;

	void build( ){
		tree.resize( 4*MAX_N, neutr );
	}

	void set( int ind, ll val, int x = 1, int lx = 0, int rx = MAX_N ){
		if( lx == rx ){
			cerr << out( lx ) << out( ind ) << out( val ) << endl;
			chkmax( tree[x], val );
			cerr << out( tree[x] ) << endl;
			return;
		}
		int m = ( lx + rx ) >> 1;
		if( ind <= m ) set( ind, val, 2*x, lx, m );
		else set( ind, val, 2*x +1, m+1, rx );

		tree[x] = std::max( tree[2*x], tree[2*x +1] );
	}


	ll query( int l, int r, int x = 1, int lx = 0, int rx = MAX_N ){
		if( l > rx || lx > r ) return neutr;
		if( l <= lx and rx <= r ) return tree[x];

		int m = ( lx + rx ) >> 1;

		ll left = query( l, r, 2*x, lx, m );
		ll right = query( l, r, 2*x +1, m+1, rx );

		return std::max( left, right );
	}
};

SegmentTree segUp;
SegmentTree segDown;

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 < (int)v.size() ; i++ ){
		cerr << out( i ) << out( v[i].first ) << out( v[i].second.first ) << out( v[i].second.second ) << endl;
	}
	cerr << endl;

	segUp.build();
	segDown.build();

	std::vector< ll > dp( MAX_N, neutr );
	dp[0] = 0;
	segUp.set( L, -L*U + dp[0] );
	segDown.set( L, L*D + dp[0] );

	cerr << out( segUp.tree[1] ) << endl;
	cerr << out( segDown.tree[1] ) << endl;
	std::vector< ll > dp2( (int)v.size() );
	for( int i=1 ; i < (int)v.size() ; i++ ){
		int currPos = v[i].second.first;

		//cerr << out( i ) << out( currPos ) << endl;

		ll maxUp = segUp.query( currPos, MAX_N -1 );
		ll maxDown = segDown.query( 0, currPos );
		//cerr << out( maxUp ) << out( maxDown ) << endl;
		maxUp += currPos*U + v[i].second.second;

		chkmax( dp[currPos], maxUp );

		maxDown += -currPos*D + v[i].second.second;
		chkmax( dp[currPos], maxDown );

		dp2[i] = std::max( maxDown, maxUp );
		//cerr << out( maxUp ) << out( maxDown ) << endl;

		segUp.set( currPos, -currPos*U + dp[currPos] );
		segDown.set( currPos, currPos*D + dp[currPos] );

		//cerr << out( i ) << out( dp[currPos] ) << endl;
	}

	std::cout << dp[L] << endl;

	/*
	std::vector< ll > dp1( (int)v.size() );
	for( int i=1 ; i < (int)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 = dp1[j] - cost + v[i].second.second;
			//cerr << out( j ) << out( A ) << endl;

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

	cerr << std::max( dp1[ v.size() -1 ], 0LL ) << endl;
	for( int i=0 ; i < (int)v.size() ; i++ ){
		cerr << out( i ) << out( dp1[i] ) << out( dp2[i] ) << endl;
	}
	cerr << endl;
	*/

	return 0;
}

• Subtask 1: 62 / 100