Submission #399421

#	Time	Username	Problem	Language	Result	Execution time	Memory
399421		CaroLinda	Salesman (IOI09_salesman)	C++14	100 / 100	560 ms	51404 KiB

salesman

#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define ll long long

const int MAX = 5e5+10 ;
const ll inf = 1e15+10 ;

using namespace std ;

struct Bit
{
	ll bit[MAX] ;
	bool type ;

	Bit(bool type = false ) : type(type) {}
	void ini() { for(int i = 0 ; i < MAX ; i++ ) bit[i] = -inf ; }

	void upd(int i , ll val ) 
	{
		if( type ) for(; i < MAX ; i += i &-i ) bit[i] = max(bit[i] , val ) ;
		else for(; i > 0 ; i -= i &-i ) bit[i] = max(bit[i] , val ) ;
	}
	ll qry(int i)
	{
		ll tot = -inf ;
	
		if(type) for(; i > 0 ; i -= i &-i ) tot = max(tot, bit[i]) ;
		else for(; i < MAX ; i += i &-i ) tot = max(tot, bit[i]) ;

		return tot ;
	}

} goingUp(1) , goingDown(0) ;

int N , S , R , maxDay ;
int day[MAX] ;
ll U , D , T ;
ll profit[MAX] , dp[MAX] , dpAux[MAX] , fat[MAX] ;
vector<int> sweepDay[MAX] ;

int main()
{	
	scanf("%d %lld %lld %d", &N, &U, &D, &S ) ;

	R = S ;

	goingUp.ini() ;
	goingDown.ini() ;

	sweepDay[0].push_back(S) ;

	for(int i = 1 , dia , loc , p ; i <= N ; i++ )
	{
		scanf("%d %d %d", &dia, &loc, &p ) ;

		profit[loc] = p ;
		maxDay = max(maxDay, dia) ;
		sweepDay[ dia ].push_back(loc) ;
		R= max(loc, R) ;
	}

	goingUp.upd( S , U*(S-R) ) ;
	goingDown.upd( S , -D*S ) ;

	for(int i = maxDay ; i >= 0 ; i-- )
	{
		for(auto e : sweepDay[i] )
		{

			ll up = goingUp.qry( e ) + U*(R-e) ;
			ll down = goingDown.qry( e ) + D*e ;

			dp[e] = max(up, down) + profit[e] ;
			dpAux[e] = dp[e] ;
		}	

		ll mx = -inf ;
		ll sumProfits = 0 ;

		sort(all(sweepDay[i])) ;
		
		for(int j = 0 ; j < sz(sweepDay[i]) ; j++ )
		{
			fat[ sweepDay[i][j] ] = sumProfits - D*sweepDay[i][j] + dp[ sweepDay[i][j] ] ;
			sumProfits += profit[ sweepDay[i][j] ] ;
		}

		T = sumProfits ;
		sumProfits = 0 ;	

		for(int j = sz(sweepDay[i])-1 , e ; j >= 0 ; j-- )
		{
			e = sweepDay[i][j] ;

			sumProfits += profit[e] ;
			dpAux[ e ] = max( dpAux[e] , mx+D*e-(T-sumProfits) ) ;
			mx = max(mx, fat[e]) ;
		}

		//for(auto e : sweepDay[i]) cout << e <<" " << fat[e] << " " << dp[e] << endl ; 

		sumProfits = 0 ;
		mx = -inf ;

		for(int j = sz(sweepDay[i])-1 , e ; j >= 0 ; j-- )
		{
			e = sweepDay[i][j] ;
			fat[e] = sumProfits - U*(R-e) + dp[e] ;
			sumProfits += profit[e] ;
		}

		sumProfits = 0 ;
		for(int j = 0 , e ; j < sz(sweepDay[i]) ; j++ )
		{
			e = sweepDay[i][j] ;
			
			sumProfits += profit[e] ;
			dpAux[e] = max( dpAux[e] , mx+U*(R-e)-(T-sumProfits) ) ;
			mx = max(mx, fat[e] ) ;
		}

		for(auto e : sweepDay[i] ) 
		{
			dp[e] = max(dp[e] , dpAux[e] ) ;

			goingUp.upd( e , dp[e]+U*(e-R) ) ;
			goingDown.upd( e , dp[e]-D*e ) ;
		}
	}

	printf("%lld\n" , dp[S] ) ;

}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  scanf("%d %lld %lld %d", &N, &U, &D, &S ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |   scanf("%d %d %d", &dia, &loc, &p ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100