Cod sursa(job #173689)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 7 aprilie 2008 22:44:17
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>
#include <algorithm>
#define N 2001
using namespace std;
int n,C;
struct carnat {int t,p;};
carnat v[N];
void scan()
{
	freopen("carnati.in", "r",stdin);
	freopen("carnati.out", "w",stdout);
	scanf("%d%d", &n,&C);
	for(int i=1;i<=n;++i)
		scanf("%d%d", &v[i].t,&v[i].p);
}
bool comp(const carnat &x, const carnat &y) 
{  
    if(x.t<y.t)  
        return true;  
   return false;  
} 
void solve()
{
	int oldS=0,Cd,max=0,lastS;
	sort(v+1,v+n+1, comp);
	//v[0].p=v[0].t=-N;
	for(int i=1;i<=n;++i,oldS=0)  
    {  
		for(int j=1;j<=n;++j)  
        {  
			if(v[j].p>=v[i].p) 
				Cd=v[i].p;  
			else 
				Cd=0;  
			lastS=oldS-(v[j].t-v[j-1].t)*C+Cd;  
			if(lastS < Cd-C) 
				lastS=Cd-C;  
			oldS=lastS;  
			if(lastS > max) 
				max=lastS; 
		}  
    } 
	printf("%d\n", max);
}
int main()
{
	scan();
	solve();
	return 0;
}