Submission #287381

#	Time	Username	Problem	Language	Result	Execution time	Memory
287381		Namnamseo	Salesman (IOI09_salesman)	C++17	100 / 100	800 ms	49144 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

int n;
ll cL, cR;
ll start;
const ll inf = (1ll<<60);

struct market {
	ll pos, earn;
	market(ll A=0, ll B=0){
		pos = A; earn = B;
	}
	bool operator<(const market&r) const { return pos < r.pos; }
};

struct LRTREE{
	const static int TT=524288;
	ll tL[TT<<1];
	ll tR[TT<<1];
	const static int T = 524288;
	void Init(int sz){
		for(int i=1; i<2*T; ++i) tL[i] = tR[i] = -inf;
	}
	inline void _Upd(ll tree[TT<<1], int p, ll val){
		p += T;
		while(p){
			tree[p] = max(tree[p], val); p/=2;
		}
	}
	void Upd(int p, ll val){
		_Upd(tL, p, val + cR * p);
		_Upd(tR, p, val - cL * p);
	}
	ll rmax(int type, int l, int r){
		const ll* tree = type ? tR : tL;
		ll ret = -inf;
		l+=T; r+=T;
		while(l<=r){
			if(l%2==1) ret=max(ret, tree[l++]);
			if(r%2==0) ret=max(ret, tree[r--]);
			l/=2; r/=2;
		}
		return ret;
	}
} tree;

ll DP[500002];
ll dp[500002];
typedef pair<int,market> TMP;

TMP asdf[500002];
market mark[500002];

int main()
{
	read(n, cL, cR, start);
	
	for(int i=0; i<n; ++i){
		ll day, pos, earn;
		read(day, pos, earn);
		asdf[i] = {day, market(pos, earn)};
	}
	sort(asdf, asdf+n);
	
	tree.Init(500002);
	tree.Upd(start, 0);
	for(int i=1; i<=500001; ++i) DP[i] = -inf;
	DP[start] = 0;
	
	for(int s=0; s<n;){
		int e;
		for(e=s+1; asdf[s].x == asdf[e].x; ++e);
		for(int i=s; i<e; ++i) mark[i-s]=asdf[i].y;
		
		int sz = e-s;		
		sort(mark, mark+sz);
		
		for(int i=0; i<sz; ++i) dp[i] = -inf;
		ll term, ps;
		
		term = -inf; ps = 0;
		for(int i=0; i<sz; ++i){
			int p = mark[i].pos;
			term = max(term, tree.rmax(1, p, 500001) + (cL * p + cR * p - ps));
			term = max(term, tree.rmax(0, 0, p) - ps);
			ps += mark[i].earn;
			dp[i] = max(dp[i], term + ps - cR * p);
		}
		
		term = -inf; ps = 0;
		for(int i=sz-1; i>=0; --i){
			int p = mark[i].pos;
			term = max(term, tree.rmax(0, 0, p) - (cL * p + cR * p + ps));
			term = max(term, tree.rmax(1, p, 500001) - ps);
			ps += mark[i].earn;
			dp[i] = max(dp[i], term + ps + cL * p);
		}
		
		for(int i=0; i<sz; ++i){
			int p = mark[i].pos;
			tree.Upd(p, dp[i]);
			DP[p] = max(DP[p], dp[i]);
		}
		s = e;
	}
	
	ll ans = -inf;
	for(int i=1; i<=500001; ++i){
		ans = max(ans, DP[i] - (i < start ? (start-i)*1LL*cR : (i-start)*1LL*cL));
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'void read(int&)':
salesman.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    6 | void read(int& x){ scanf("%d",&x); }
      |                    ~~~~~^~~~~~~~~
salesman.cpp: In function 'void read(ll&)':
salesman.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 | void read(ll& x){ scanf("%lld",&x); }
      |                   ~~~~~^~~~~~~~~~~

• Subtask 1: 100 / 100