oj.uz

Submission #399421

# Submission time Handle Problem Language Result Execution time Memory
399421 2021-05-05T18:25:18 Z CaroLinda Salesman (IOI09_salesman) C++14
100 / 100
 560 ms 51404 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19916 KB Output is correct
2 Correct 11 ms 19916 KB Output is correct
3 Correct 11 ms 20032 KB Output is correct
4 Correct 12 ms 20044 KB Output is correct
5 Correct 13 ms 20220 KB Output is correct
6 Correct 37 ms 36136 KB Output is correct
7 Correct 68 ms 37092 KB Output is correct
8 Correct 125 ms 38596 KB Output is correct
9 Correct 165 ms 40152 KB Output is correct
10 Correct 296 ms 44908 KB Output is correct
11 Correct 394 ms 44912 KB Output is correct
12 Correct 436 ms 48040 KB Output is correct
13 Correct 431 ms 47940 KB Output is correct
14 Correct 560 ms 51404 KB Output is correct
15 Correct 472 ms 51172 KB Output is correct
16 Correct 531 ms 51160 KB Output is correct
17 Correct 11 ms 19788 KB Output is correct
18 Correct 11 ms 19916 KB Output is correct
19 Correct 11 ms 19916 KB Output is correct
20 Correct 12 ms 19968 KB Output is correct
21 Correct 13 ms 19916 KB Output is correct
22 Correct 13 ms 20044 KB Output is correct
23 Correct 13 ms 20076 KB Output is correct
24 Correct 13 ms 20036 KB Output is correct
25 Correct 86 ms 36036 KB Output is correct
26 Correct 153 ms 36604 KB Output is correct
27 Correct 258 ms 37268 KB Output is correct
28 Correct 258 ms 35032 KB Output is correct
29 Correct 369 ms 37956 KB Output is correct
30 Correct 373 ms 38404 KB Output is correct