Cod sursa(job #323960)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 14 iunie 2009 11:53:33
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <cstdio>
#include <algorithm>
#define vm 2000000100
using namespace std;

struct vec
{
	int t, p;
} v[2010];

int n, c, k, s, r;

int cmp(vec a, vec b)
{
	return (a.t<b.t);
}

int main()
{
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	scanf("%d %d",&n,&c);
	int i;
	for (i=1; i<=n; i++) scanf("%d %d",&v[i].t,&v[i].p);
	sort(v+1, v+n+1, cmp);
	int j, x;
	v[0].t=v[1].t-1;
	for (i=1; i<=n; i++)
	{
		s=0;
		for (j=1; j<=n; j++)
		{
			if (v[j].p>=v[i].p) k=v[i].p; else k=0;
			s=max(s-(v[j].t-v[j-1].t)*c+k, k-c);
			if (s>r) r=s;
		}
	}
	printf("%d",r);
}