oj.uz

답안 #121470

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
121470 2019-06-26T14:23:40 Z TadijaSebez Salesman (IOI09_salesman) C++11
100 / 100
 824 ms 33080 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8548 KB Output is correct
2 Correct 8 ms 8448 KB Output is correct
3 Correct 8 ms 8548 KB Output is correct
4 Correct 9 ms 8548 KB Output is correct
5 Correct 15 ms 8704 KB Output is correct
6 Correct 30 ms 9600 KB Output is correct
7 Correct 61 ms 10976 KB Output is correct
8 Correct 131 ms 13444 KB Output is correct
9 Correct 185 ms 15580 KB Output is correct
10 Correct 335 ms 22628 KB Output is correct
11 Correct 409 ms 23160 KB Output is correct
12 Correct 569 ms 27144 KB Output is correct
13 Correct 824 ms 27432 KB Output is correct
14 Correct 768 ms 33080 KB Output is correct
15 Correct 660 ms 32172 KB Output is correct
16 Correct 774 ms 32200 KB Output is correct
17 Correct 9 ms 8448 KB Output is correct
18 Correct 8 ms 8576 KB Output is correct
19 Correct 9 ms 8576 KB Output is correct
20 Correct 10 ms 8576 KB Output is correct
21 Correct 10 ms 8576 KB Output is correct
22 Correct 13 ms 8704 KB Output is correct
23 Correct 13 ms 8704 KB Output is correct
24 Correct 13 ms 8704 KB Output is correct
25 Correct 118 ms 13048 KB Output is correct
26 Correct 215 ms 17564 KB Output is correct
27 Correct 387 ms 23928 KB Output is correct
28 Correct 472 ms 24820 KB Output is correct
29 Correct 600 ms 30708 KB Output is correct
30 Correct 623 ms 31480 KB Output is correct