Cod sursa(job #599786)

Utilizator maritimCristian Lambru maritim Data 29 iunie 2011 16:29:01
Problema Carnati Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define MaxN 2100
#define ll long long
#define maximul MaxPrice[i-1] - (A[i].Timp - A[i-1].Timp) * C + Max[i-1]

typedef struct
{
	int Price;
	int Timp;
} cump;

cump A[MaxN];
ll MaxPrice[MaxN];
ll Max[MaxN];
int MaxTimp[MaxN];
int B[MaxN];
int N;
int C;
ll MAX;

bool cmp(cump a,cump b)
{
	return a.Timp < b.Timp;
}

int max(int a,int b)
{
	return a>b ? a:b;
}

int main()
{
	FILE *f = fopen("carnati.in","r");
	FILE *g = fopen("carnati.out","w");
	
	fscanf(f,"%d %d",&N,&C);
	for(int i=1;i<=N;i++)
		fscanf(f,"%d %d",&A[i].Timp,&A[i].Price);
	sort(A+1,A+N+1,cmp);
	for(int i=1;i<=N;i++)
	{
		Max[i] = A[i].Price - C;
		MaxPrice[i] = A[i].Price;
		MaxTimp[i] = 1;
		B[i] = 1;
		if(MaxPrice[i-1] - (A[i].Timp - A[i-1].Timp) * C + Max[i-1] > Max[i] && MaxPrice[i] >= MaxPrice[i-1])
		{
			MaxPrice[i] = MaxPrice[i-1];
			Max[i] = maximul;
			B[i] = B[i-1] + 1;
			MaxTimp[i] = MaxTimp[i-1] + A[i].Timp - A[i-1].Timp;
		}
		if(Max[i-1] - (A[i].Timp - A[i-1].Timp) * C > Max[i] && MaxPrice[i] < MaxPrice[i-1])
		{
			MaxPrice[i] = MaxPrice[i-1];
			Max[i] = Max[i-1] - (A[i].Timp - A[i-1].Timp) * C;
			B[i] = B[i-1];
			MaxTimp[i] = MaxTimp[i-1] + A[i].Timp - A[i-1].Timp;
		}
		if(MaxPrice[i] * (B[i-1] + 1) - C * (MaxTimp[i-1] + A[i].Timp - A[i-1].Timp) > Max[i] && MaxPrice[i] < MaxPrice[i-1])
		{
			Max[i] = MaxPrice[i] * (B[i-1] + 1) - C * (MaxTimp[i-1] + A[i].Timp - A[i-1].Timp);
			B[i] = B[i-1];
			MaxTimp[i] = MaxTimp[i-1] + A[i].Timp - A[i-1].Timp;
		}
	}
	for(int i=1;i<=N;i++)
		if(MAX < Max[i])
			MAX = Max[i];
	fprintf(g,"%llu ",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}