Submission #408731

#	Time	Username	Problem	Language	Result	Execution time	Memory
408731		Jasiekstrz	Salesman (IOI09_salesman)	C++17	60 / 100	751 ms	36016 KiB

salesman

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=(int)5e5+1;
const int P=6e5;
const int INF=2e9+7;
struct Tree
{
	int pot;
	int t[2*P+10];
	void init(int _pot)
	{
		pot=_pot;
		for(int i=1;i<=2*pot;i++)
			t[i]=-INF;
		return;
	}
	void upd(int x,int c)
	{
		for(x+=pot-1;x>0;x/=2)
			t[x]=max(t[x],c);
		return;
	}
	int read(int l,int r)
	{
		int ans=-INF;
		for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
		{
			if(l%2==1)
				ans=max(ans,t[l++]);
			if(r%2==0)
				ans=max(ans,t[r--]);
		}
		return ans;
	}
};
vector<pair<int,int>> fair[N+10];
Tree up,down;
int read(int x,int u,int d)
{
	return max(up.read(x,N)+x*u,down.read(1,x)-x*d);
}
void upd(int x,int c,int u,int d)
{
	up.upd(x,c-x*u);
	down.upd(x,c+x*d);
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,d,u,s;
	cin>>n>>u>>d>>s;
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		fair[a].emplace_back(b,c);
	}
	int pot;
	for(pot=1;pot<N;pot*=2);
	up.init(pot);
	down.init(pot);
	upd(s,0,u,d);
	for(int i=1;i<=N;i++)
	{
		if(fair[i].empty())
			continue;
		sort(fair[i].begin(),fair[i].end());
		vector<int> w(fair[i].size(),-INF);
		int tmp=-INF;
		for(size_t j=0;j<fair[i].size();j++)
		{
			int xd=read(fair[i][j].fi,u,d)+fair[i][j].se;
			if(j>0)
				xd=max(xd,tmp+d*(fair[i][j].fi-fair[i][j-1].fi)+fair[i][j].se);
			tmp=xd;
			w[j]=xd;
		}
		tmp=-INF;
		for(int j=fair[i].size()-1;j>=0;j--)
		{
			int xd=read(fair[i][j].fi,u,d)+fair[i][j].se;
			if(j<fair[i].size()-1)
				xd=max(xd,tmp+u*(fair[i][j+1].fi-fair[i][j].fi)+fair[i][j].se);
			tmp=xd;
			w[j]=max(w[j],xd);
		}
		//cerr<<i<<" "<<fair[i][0].fi<<" "<<w[0]<<"\n";
		for(size_t j=0;j<fair[i].size();j++)
			upd(fair[i][j].fi,w[j],u,d);
	}
	cout<<read(s,u,d)<<"\n";
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:87:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |    if(j<fair[i].size()-1)
      |       ~^~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100