Submission #733591

#	Time	Username	Problem	Language	Result	Execution time	Memory
733591		penguin133	Salesman (IOI09_salesman)	C++17	60 / 100	1636 ms	52904 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, u, d, s;
int dp[500005];
pii A[500005];
/*
struct node{
	int s, e, val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e,  val = -1e18;
		if(s != e)l = new node(s, (s + e) >> 1), r = new node(((s + e) >> 1)+1, e);
	}
	void upd(int p, int v){
		if(s == e)val = max(val, v);
		else{
			if(p <= (s + e) >> 1)l->upd(p, v);
			else r->upd(p, v);
			val = max(l->val, r->val);
		}
	}
	int qry(int a, int b){
		if(s == a && b == e)return val;
		else if(b <= (s + e) >> 1)return l->qry(a, b);
		else if(a > (s + e) >> 1)return r->qry(a, b);
		else return max(l->qry(a, (s + e) >> 1), r->qry(((s + e) >> 1) +1, b));
	}
}*dwn, *up;
*/
int dwn[2000005], up[2000005], tmp[2000005], tmp2[2000005], dp2[500005];
void build(int t[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = -1e18;
    } else {
        int tm = (tl + tr) / 2;
        build(t, v*2, tl, tm);
        build(t, v*2+1, tm+1, tr);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
 
void update(int t[], int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = max(t[v], new_val);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(t, v*2, tl, tm, pos, new_val);
        else
            update(t, v*2+1, tm+1, tr, pos, new_val);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
 
void upd(int t[], int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            upd(t, v*2, tl, tm, pos, new_val);
        else
            upd(t, v*2+1, tm+1, tr, pos, new_val);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
 
int sum(int t[], int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return -1e18;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return max(sum(t, v*2, tl, tm, l, min(r, tm)),
           sum(t, v*2+1, tm+1, tr, max(l, tm+1), r));
}
 
void solve(){
	cin >> n >> u >> d >> s;
	int mx = s;
	for(int i=1;i<=n;i++){
		cin >> A[i].fi >> A[i].se.fi >> A[i].se.se;
		mx = max(mx, A[i].se.fi);
	}
	sort(A+1, A+n+1);
	A[0].se.fi = s;
	A[n+1].se.fi = s;
	build(dwn, 1, 1, mx );
	build(up, 1, 1, mx );
	update(dwn, 1, 1, mx, s, -d * s);
	update(up, 1, 1, mx, s, u * s);
	build(tmp, 1, 1, mx);
	build(tmp2, 1, 1, mx);
	for(int i=1;i<=n+1;i++){
		int j = i + 1;
		while(j <= n && A[j].fi == A[i].fi)j++;
		j--;
		for(int x=j;x>=i;x--){
			int top = max(sum(dwn, 1, 1, mx, A[x].se.fi, mx), sum(tmp, 1, 1, mx, A[x].se.fi, mx)) + d * A[x].se.fi + A[x].se.se;
			int bot = max(sum(up, 1, 1, mx, 1, A[x].se.fi), sum(tmp2, 1, 1, mx, 1, A[x].se.fi)) - u * A[x].se.fi + A[x].se.se;
			dp2[i] = max(top, bot);
			update(tmp, 1, 1, mx, A[x].se.fi, dp2[i] - d * A[x].se.fi);
			update(tmp2, 1, 1, mx, A[x].se.fi, dp2[i] + u * A[x].se.fi);
		}
		for(int x=i;x<=j;x++){
			int top = max(sum(dwn, 1, 1, mx, A[x].se.fi, mx), (int)-1e18) + d * A[x].se.fi + A[x].se.se;
			int bot = max(sum(up, 1, 1, mx, 1, A[x].se.fi), (int)-1e18) - u * A[x].se.fi + A[x].se.se;
			dp[i] = max(top, bot);
			update(dwn, 1, 1, mx, A[x].se.fi, dp[i] - d * A[x].se.fi);
			update(up, 1, 1, mx, A[x].se.fi, dp[i] + u * A[x].se.fi);
		}
		for(int x=i;x<=j;x++)dp[i] = max(dp[i], dp2[i]);
		for(int x=i;x<=j;x++){
			update(dwn, 1, 1, mx, A[x].se.fi, dp[i] - d * A[x].se.fi);
			update(up, 1, 1, mx, A[x].se.fi, dp[i] + u * A[x].se.fi);
			upd(tmp, 1, 1, mx, A[x].se.fi, -1e18);
			upd(tmp2, 1, 1, mx, A[x].se.fi, -1e18);
		}
      	i = j;
		//int top = dwn->qry(A[i].se.fi, mx) + d * A[i].se.fi + A[i].se.se;
		//int bot = up->qry(1, A[i].se.fi) - u * A[i].se.fi + A[i].se.se;
		/*
		for(int j=i-1;j>=0;j--){
			int cst;
			if(A[j].se.fi > A[i].se.fi)cst = d * (A[j].se.fi - A[i].se.fi);
			else cst = u * (A[i].se.fi - A[j].se.fi);
			dp[i] = max(dp[i], dp[j] - cst + A[i].se.se);
		}
		*/
		//dwn->upd(A[i].se.fi, dp[i] - d * A[i].se.fi);
		//up->upd(A[i].se.fi, dp[i] + u * A[i].se.fi);
	}
	cout << dp[n+1];
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

salesman.cpp:147:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  147 | main(){
      | ^~~~

• Subtask 1: 60 / 100