Cod sursa(job #551676)

Utilizator cnt_tstcont teste cnt_tst Data 10 martie 2011 22:49:21
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxN 2005

FILE*f=fopen("carnati.in","r");
FILE*g=fopen("carnati.out","w");

int N,C,i,Pret,Smax,S,ii,up;

struct client{
	int T;
	int P;
}A[maxN];

int cmp ( client a, client b ){
	return a.T < b.T ;
}

int  main () {
	fscanf(f,"%d %d",&N,&C);
	for ( i = 1 ; i <= N ; ++i ){
		fscanf(f,"%d %d",&A[i].T,&A[i].P);
	}
	sort( A + 1 , A + N + 1, cmp);
	
	for ( ii = 1 ; ii <= N ; ++ii ){
		Pret = A[ii].P;
		S = 0; up = 0;
		
		for ( i = 1 ; i <= N ; ++i ){
			if ( A[i].P < Pret )	continue;
			if ( !up ){
				S = Pret;
				if ( S > Smax )
					Smax = S;
				up = i;
				continue;
			}
			if ( S + Pret - (A[i].T - A[up].T ) * C > Pret )
				S = S + Pret - (A[i].T - A[up].T ) * C ;
			else
				S = Pret;
			up = i;
			if ( S - C > Smax )
				Smax = S - C;
		}
	}
	fprintf(g,"%d\n",Smax);
	
	fclose(f);
	fclose(g);
	
	return 0;
}