Submission #399414

#	Time	Username	Problem	Language	Result	Execution time	Memory
399414		CaroLinda	Salesman (IOI09_salesman)	C++14	60 / 100	507 ms	52420 KiB

salesman

#include <bits/stdc++.h>

#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 ;
ll profit[MAX] , dp[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] ;

//			cout << dp[e] << " " << up <<" " << down << endl ;
		}	
		for(auto e : sweepDay[i] ) 
		{
			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:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf("%d %lld %lld %d", &N, &U, &D, &S ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   scanf("%d %d %d", &dia, &loc, &p ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100