Cod sursa(job #383724)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 17 ianuarie 2010 21:16:01
Problema Carnati Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
#define infile "carnati.in"
#define outfile "carnati.out"
#define nmax 2013
struct client
{
	int b; //bani
	int t; //timp
}c[nmax];
int n; //numarul de clienti
int a; //costul angajatului per timp
int pmax; //profitul maxim

inline int max(int a, int b)
{
	if(a>b) return a; return b;
}

void swap(struct client *a, struct client *b)
{
	struct client c=*a; *a=*b; *b=c;
}

void read()
{
	int i;
	scanf("%d %d\n",&n,&a);
	for(i=1;i<=n;i++)
		scanf("%d %d\n",&c[i].t,&c[i].b);
}

void sort()
{
	int i,j;
	
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			if(c[i].t > c[j].t)
				swap(&c[i],&c[j]);
}

void solve()
{
	int i,j,k,pret,profit;
	
	for(i=1;i<=n;i++)
	{ //luam toate preturile clientilor
		//pretul carnatului
		pret=c[i].b;
		
		//cautam primul client ce poate cumpara
		for(j=1;c[j].b<pret;j++);
		
		//salvam profitul cu primul client
		profit=pret-a;
		
		//vedem daca este profitul maxim
		pmax=max(pmax,profit);
		
		//verificam restul clientilor
		for(k=j,j++;j<=n;j++)
			if(c[j].b >= pret)
				pmax=max(pmax,profit=max(profit + pret - a*(c[j].t-c[k].t),pret-a)),k=j;
	}
}

void write()
{
	printf("%d\n",pmax);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	sort();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}