oj.uz

Submission #287381

# Submission time Handle Problem Language Result Execution time Memory
287381 2020-08-31T16:34:08 Z Namnamseo Salesman (IOI09_salesman) C++17
100 / 100
 800 ms 49144 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 26 ms 40192 KB Output is correct
2 Correct 24 ms 40184 KB Output is correct
3 Correct 26 ms 40192 KB Output is correct
4 Correct 27 ms 40192 KB Output is correct
5 Correct 29 ms 40312 KB Output is correct
6 Correct 53 ms 40576 KB Output is correct
7 Correct 114 ms 41080 KB Output is correct
8 Correct 183 ms 42108 KB Output is correct
9 Correct 256 ms 42616 KB Output is correct
10 Correct 406 ms 45048 KB Output is correct
11 Correct 523 ms 45560 KB Output is correct
12 Correct 668 ms 46384 KB Output is correct
13 Correct 636 ms 46584 KB Output is correct
14 Correct 797 ms 49144 KB Output is correct
15 Correct 636 ms 48248 KB Output is correct
16 Correct 800 ms 48248 KB Output is correct
17 Correct 23 ms 40192 KB Output is correct
18 Correct 23 ms 40192 KB Output is correct
19 Correct 24 ms 40192 KB Output is correct
20 Correct 25 ms 40192 KB Output is correct
21 Correct 26 ms 40192 KB Output is correct
22 Correct 28 ms 40312 KB Output is correct
23 Correct 29 ms 40312 KB Output is correct
24 Correct 28 ms 40320 KB Output is correct
25 Correct 160 ms 41592 KB Output is correct
26 Correct 287 ms 43304 KB Output is correct
27 Correct 457 ms 45176 KB Output is correct
28 Correct 512 ms 46072 KB Output is correct
29 Correct 702 ms 46840 KB Output is correct
30 Correct 653 ms 48248 KB Output is correct