Submission #328535

#	Time	Username	Problem	Language	Result	Execution time	Memory
328535		tzxydby	Salesman (IOI09_salesman)	C++11	60 / 100	1039 ms	44220 KiB

salesman

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005,inf=500001;
struct seg
{
	int tr[N<<3];
	void build(int k,int l,int r)
	{
		tr[k]=-1e18;
		if(l==r)
			return;
		int mid=l+r>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
	}
	void update(int k,int l,int r,int x,int v)
	{
		if(l==r)
		{
			tr[k]=v;
			return;
		}
		int mid=l+r>>1;
		if(x<=mid) update(k<<1,l,mid,x,v);
		else update(k<<1|1,mid+1,r,x,v);
		tr[k]=max(tr[k<<1],tr[k<<1|1]);
	}
	int query(int k,int l,int r,int a,int b)
	{
		if(l==a&&r==b)
			return tr[k];
		int mid=l+r>>1;
		if(b<=mid) return query(k<<1,l,mid,a,b);
		else if(a>mid) return query(k<<1|1,mid+1,r,a,b);
		else return max(query(k<<1,l,mid,a,mid),query(k<<1|1,mid+1,r,mid+1,b));
	}
}s1,s2;
int n,u,d,s,ans;
vector<pair<int,int>>a[N];
signed main()
{
	ios::sync_with_stdio(false);
	cin>>n>>u>>d>>s;
	for(int i=1;i<=n;i++)
	{
		int t,l,w;
		cin>>t>>l>>w;
		a[t].emplace_back(l,w);		
	}
	s1.build(1,1,inf);
	s2.build(1,1,inf);
	s1.update(1,1,inf,s,d*s);
	s2.update(1,1,inf,s,-u*s);
	for(int i=1;i<=inf;i++)
	{
		if(a[i].size()==0)
			continue;
		sort(a[i].begin(),a[i].end());
		int m=a[i].size(),t;
		vector<int>b(m),y(m),z(m);
		for(int j=0;j<m;j++)
		{
			int x=a[i][j].first,w=a[i][j].second;
			b[j]=max(s1.query(1,1,inf,1,x)-x*d,s2.query(1,1,inf,x,inf)+x*u)+w;
		}
		t=b[0];
		for(int j=0;j<m;j++)
		{
			int x=a[i][j].first,w=a[i][j].second;
			if(j) t=max(t-(x-a[i][j-1].first)*d+w,b[i]);
			y[j]=t;
		}
		t=b[m-1];
		for(int j=m-1;j>=0;j--)
		{
			int x=a[i][j].first,w=a[i][j].second;
			if(j!=m-1) t=max(t-(a[i][j+1].first-x)*u+w,b[i]);
			z[j]=t;
		}
		for(int j=0;j<m;j++)
		{
			b[j]=max(y[j],z[j]);
			int x=a[i][j].first;
			s1.update(1,1,inf,x,b[j]+d*x);
			s2.update(1,1,inf,x,b[j]-u*x);
			ans=max(ans,b[j]-(x>s?u*(x-s):d*(s-x)));
		}
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

salesman.cpp: In member function 'void seg::build(long long int, long long int, long long int)':
salesman.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |   int mid=l+r>>1;
      |           ~^~
salesman.cpp: In member function 'void seg::update(long long int, long long int, long long int, long long int, long long int)':
salesman.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid=l+r>>1;
      |           ~^~
salesman.cpp: In member function 'long long int seg::query(long long int, long long int, long long int, long long int, long long int)':
salesman.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid=l+r>>1;
      |           ~^~

• Subtask 1: 60 / 100