Submission #1156716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156716		Doncho_Bonboncho	Salesman (IOI09_salesman)	C++20	60 / 100	662 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() );

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

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

	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 currInd = i;
		std::vector< int > currSales;
		while( currInd < (int)v.size() and v[currInd].first == v[i].first ){
			currInd ++;
		}

		for( int j=i ; j < currInd ; j++ ){

			int currPos = v[j].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;

			chkmax( dp[currPos], maxUp );
			maxDown += -currPos*D;
			chkmax( dp[currPos], maxDown );
		}

		for( int j=currInd-1 ; j >= i ; j-- ){

			int currPos = v[j].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;

			chkmax( dp[currPos], maxUp );
			maxDown += -currPos*D;
			chkmax( dp[currPos], maxDown );
		}

		for( int j=i ; j < currInd ; j++ ) dp[v[j].second.first] += v[j].second.second;

		for( int j=i ; j < currInd ; j++ ){
			int currPos = v[j].second.first;
			segUp.set( currPos, -currPos*U + dp[currPos] );
			segDown.set( currPos, currPos*D + dp[currPos] );
		}

		i = currInd-1;

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

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

	return 0;
}

• Subtask 1: 60 / 100