Submission #203861

#	Time	Username	Problem	Language	Result	Execution time	Memory
203861		jjaewon	Salesman (IOI09_salesman)	C++14	20 / 100	427 ms	16504 KiB

salesman

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int base=1<<19;

int N,D,U,S,dp[500010],Dtree[1<<20],Utree[1<<20];
struct market{ int T,L,M; }d[500010];
bool cmp(const market &p1,const market &p2){ return p1.T==p2.T?p1.L<p2.L:p1.T<p2.T; };

int query(int (&tree)[1<<20],int l,int r){
	l+=base; r+=base;
	int ret=-inf;
	while(l<=r){
		if(l&1) ret=max(ret,tree[l]);
		if(~r&1) ret=max(ret,tree[r]);
		l=(l+1)>>1; r=(r-1)>>1;
	}
	return ret;
}

void update(int (&tree)[1<<20],int p,int v){
	p+=base-1;
	while(p>>=1) tree[p]=max(tree[p],v);
}
/*
int query(int (&tree)[1<<20],int l,int r){
	int ret=-inf;
	for(;l<=r;l++) ret=max(ret,tree[l]);
	return ret;
}

void update(int (&tree)[1<<20],int p,int v){
	tree[p]=v;
}
*/


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>N>>D>>U>>S;
    for(int i=1;i<=N;i++) cin>>d[i].T>>d[i].L>>d[i].M;
    sort(d+1,d+N+1,cmp);
	d[0]={0,S,0}; d[N+1]={500010,S,0};
	for(int i=0;i<(1<<20);i++) Dtree[i]=Utree[i]=-inf;
	update(Dtree,d[0].L,dp[0]-d[0].L*D);
	update(Utree,d[0].L,dp[0]+d[0].L*U);
	for(int i=1;i<=N+1;i++){
		dp[i]=max(query(Dtree,d[i].L,500000)+d[i].L*D,query(Utree,0,d[i].L-1)-d[i].L*U)+d[i].M;
		update(Dtree,d[i].L,dp[i]-d[i].L*D);
		update(Utree,d[i].L,dp[i]+d[i].L*U);
	}
	cout<<dp[N+1];
    return 0;
}

• Subtask 1: 20 / 100