Cod sursa(job #599783)

Utilizator maritimCristian Lambru maritim Data 29 iunie 2011 16:21:44
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<stdio.h>

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

int Price[MaxN];
int Timp[MaxN];
ll MaxPrice[MaxN];
ll Max[MaxN];
int MaxTimp[MaxN];
int B[MaxN];
int N;
int C;
ll MAX;

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",&Timp[i],&Price[i]);
	for(int i=1;i<=N;i++)
	{
		Max[i] = Price[i] - C;
		MaxPrice[i] = Price[i];
		MaxTimp[i] = 1;
		B[i] = 1;
		if(MaxPrice[i-1] - (Timp[i] - Timp[i-1]) * 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] + Timp[i] - Timp[i-1];
		}
		if(Max[i-1] - (Timp[i] - Timp[i-1]) * C > Max[i] && MaxPrice[i] < MaxPrice[i-1])
		{
			MaxPrice[i] = MaxPrice[i-1];
			Max[i] = Max[i-1] - (Timp[i] - Timp[i-1]) * C;
			B[i] = B[i-1];
			MaxTimp[i] = MaxTimp[i-1] + Timp[i] - Timp[i-1];
		}
		if(MaxPrice[i] * (B[i-1] + 1) - C * (MaxTimp[i-1] + Timp[i] - Timp[i-1]) > Max[i] && MaxPrice[i] < MaxPrice[i-1])
		{
			Max[i] = MaxPrice[i] * (B[i-1] + 1) - C * (MaxTimp[i-1] + Timp[i] - Timp[i-1]);
			B[i] = B[i-1];
			MaxTimp[i] = MaxTimp[i-1] + Timp[i] - Timp[i-1];
		}
	}
	for(int i=1;i<=N;i++)
		if(MAX < Max[i])
			MAX = Max[i];
	fprintf(g,"%llu ",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}