Submission #121470

#	Time	Username	Problem	Language	Result	Execution time	Memory
121470		TadijaSebez	Salesman (IOI09_salesman)	C++11	100 / 100	824 ms	33080 KiB

salesman

#include <stdio.h>
#include <algorithm>
using namespace std;
struct Fair
{
	int t,x,Value;
	int id;
	int i;
	int Best;
	int CurBest;
	int LowBest;
	inline bool operator < (const Fair &b) const
	{
		if(t<b.t) return true;
		if(t==b.t && x<b.x) return true;
		return false;
	}
} Fairs[500040];
bool Compare1(Fair a, Fair b)
{
	if(a.x<b.x) return true;
	return false;
}
const int Max_N=1<<19;
const int inf=1000000000;
int SegmentTree[2][Max_N*2+20];
int max(int a, int b)
{
	if(a>b) return a;
	else return b;
}
void Initialize(int st)
{
	int i;
	for(i=0;i<Max_N*2+5;i++)
		SegmentTree[st][i]=-inf;
}
void Set(int st, int index, int value)
{
	int x=Max_N+index;
	SegmentTree[st][x]=value;
	x/=2;
	while(x>0)
	{
		SegmentTree[st][x]=max(SegmentTree[st][x*2],SegmentTree[st][x*2+1]);
		x/=2;
	}
}
int Get(int st, int ss, int se, int si, int qs, int qe)
{
	if(ss>qe || se<qs) return -inf;
	if(ss>=qs && se<=qe) return SegmentTree[st][si];
	int mid=(ss+se)>>1;
	return max(Get(st,ss,mid,si*2,qs,qe),Get(st,mid+1,se,si*2+1,qs,qe));
}
int Get(int st, int qs, int qe)
{
	return Get(st,0,Max_N-1,1,qs,qe);
}
int main()
{
	int n,u,d,s,i,j;
	scanf("%i %i %i %i",&n,&u,&d,&s);
	Fairs[0].t=-1;
	Fairs[0].x=s;
	Fairs[0].Value=0;
	Fairs[0].i=0;
	int maxt=0;
	for(i=1;i<=n;i++)
	{
		scanf("%i %i %i",&Fairs[i].t,&Fairs[i].x,&Fairs[i].Value);
		maxt=max(maxt,Fairs[i].t);
		Fairs[i].i=1;
	}
	Fairs[n+1].t=maxt+1;
	Fairs[n+1].x=s;
	Fairs[n+1].Value=0;
	Fairs[n+1].i=n+1;
	n+=2;
	sort(Fairs,Fairs+n,Compare1);
	for(i=0;i<n;i++)
	{
		Fairs[i].id=i;
	}
	sort(Fairs,Fairs+n);
	Initialize(0);
	Initialize(1);
	Set(0,Fairs[0].id,d*Fairs[0].x);
	Set(1,Fairs[0].id,-u*Fairs[0].x);
	for(i=1;i<n;i++)
	{
		if(Fairs[i].t!=Fairs[i+1].t)
		{
			Fairs[i].Best=max(Get(0,0,Fairs[i].id-1)-d*Fairs[i].x,
					Get(1,Fairs[i].id+1,n)+u*Fairs[i].x)+Fairs[i].Value;
			Set(0,Fairs[i].id,Fairs[i].Best+d*Fairs[i].x);
			Set(1,Fairs[i].id,Fairs[i].Best-u*Fairs[i].x);
		}
		else
		{
			int first=i;
			int last;
			while(Fairs[i].t==Fairs[i+1].t)
				i++;
			last=i;
			for(j=first;j<=last;j++)
			{
				Fairs[j].LowBest=max(Get(0,0,Fairs[j].id-1)-d*Fairs[j].x,
					Get(1,Fairs[j].id+1,n)+u*Fairs[j].x)+Fairs[j].Value;
				Fairs[j].Best=Fairs[j].LowBest;
			}
			Fairs[first].CurBest=Fairs[first].LowBest;
			Fairs[first].Best=Fairs[first].CurBest;
			for(j=first+1;j<=last;j++)
			{
				int val=Fairs[j-1].CurBest-(Fairs[j].x-Fairs[j-1].x)*d+Fairs[j].Value;
				Fairs[j].CurBest=max(val,Fairs[j].LowBest);
				Fairs[j].Best=max(Fairs[j].Best,Fairs[j].CurBest);
			}
			Fairs[last].CurBest=Fairs[last].LowBest;
			Fairs[last].Best=max(Fairs[last].Best,Fairs[last].CurBest);
			for(j=last-1;j>=first;j--)
			{
				int val=Fairs[j+1].CurBest-(Fairs[j+1].x-Fairs[j].x)*u+Fairs[j].Value;
				Fairs[j].CurBest=max(val,Fairs[j].LowBest);
				Fairs[j].Best=max(Fairs[j].Best,Fairs[j].CurBest);
			}
			for(j=first;j<=last;j++)
			{
				Set(0,Fairs[j].id,Fairs[j].Best+d*Fairs[j].x);
				Set(1,Fairs[j].id,Fairs[j].Best-u*Fairs[j].x);
			}
		}
	}
	if(Fairs[n-1].Best<0) printf("0\n");
	else printf("%i\n",Fairs[n-1].Best);
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&n,&u,&d,&s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i %i",&Fairs[i].t,&Fairs[i].x,&Fairs[i].Value);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100