Cod sursa(job #323957)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 14 iunie 2009 11:44:39
Problema Carnati Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 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;
	for (i=1; i<=n; i++)
	{
		k=-1;
		s=0;
		for (j=1; j<=n; j++)
			if (v[j].p>=v[i].p)
			{
				if (k==-1) x=v[i].p-c; else x=v[i].p-(v[j].t-k)*c;
				if (x>0) 
				{
					k=v[j].t;
					s+=x;
				}
			}
		if (s>r) r=s;
	}
	printf("%d",r);
}