Cod sursa(job #181772)

Utilizator AndreyPAndrei Poenaru AndreyP Data 18 aprilie 2008 22:03:32
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <stdio.h>
#include <algorithm>
#define N 2001
using namespace std;
struct ca{int t,p;};
ca v[N];
int n,C;
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);
	v[0].p=v[0].t=-10;
}
bool comp(const ca &x, const ca &y)
{  
    if(x.t<y.t)  
        return true;  
   return false;  
} 
void solve()
{
	int oldS,Cd,maxi=0,lastS;
	sort(v+1,v+n+1, comp);
	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 > maxi) 
				maxi=lastS; 
		}  
    } 
	printf("%d\n", maxi);
}
int main()
{
	scan();
	solve();
	return 0;
}