Cod sursa(job #599828)

Utilizator maritimCristian Lambru maritim Data 29 iunie 2011 17:54:30
Problema Carnati Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define MaxN 2100
#define ll long long

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

cump A[MaxN];
int H[MaxN];
int N;
int C;
int sol;
int MAX;

bool cmp(cump a,cump b)
{
	if(a.Timp == b.Timp)
		return a.Price > b.Price;
	return a.Timp < b.Timp;
}

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

int min(int a,int b)
{
	return a<b ? a:b;
}

int solve(int a)
{
	int MAX = 0;
	int S = 0;
	for(int i=1;i<=N;i++)
	{
		if(S <= 0)
		{
			if(A[i].Price >= A[a].Price)
				S = A[a].Price - min(C , C * H[i]);
		}
		else
		{
			if(A[i].Price >= A[a].Price)
				S += max(A[a].Price - H[i] * C , A[a].Price - min(C , C * H[i]));
		}
		if(MAX < S)
			MAX = S;
	}
	return MAX;
}

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);
	H[1] = 1;
	for(int i=2;i<=N;i++)
		H[i] = A[i].Timp - A[i-1].Timp;
	for(int i=1;i<=N;i++)
	{
		sol = solve(i);
		if(MAX < sol)
			MAX = sol;
	}
	fprintf(g,"%d ",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}