Cod sursa(job #180320)

Utilizator mihai0110Bivol Mihai mihai0110 Data 16 aprilie 2008 21:22:29
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#include<algorithm>
#define MAXN 1<<11

using namespace std;

struct om{int t,p;} v[MAXN];
int i,j,n,c,cnt,pr,max,g,sol=-2000000000;
int a[MAXN];

bool comp(const om &a,const om &b)
{
		 return a.t<b.t;
} 

int main(void)
{
		freopen("carnati.in","r",stdin);
		freopen("carnati.out","w",stdout);
		scanf("%d%d",&n,&c);
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&v[i].t,&v[i].p);
		}
		sort(v+1,v+n+1,comp);
		a[0]=v[0].t=-10;
		for(cnt=1;cnt<=n;cnt++)
		{
      pr=v[cnt].p; 
			for(i=1;i<=n;i++)
			{
				if(v[i].p>=pr)
					g=pr;
				else
					g=0;
				a[i]=a[i-1]-(v[i].t-v[i-1].t)*c+g;
				if(g-c>a[i])
					a[i]=g-c;
				if(a[i]>sol)
					sol=a[i];
			}
     }
		printf("%d\n",sol);
		return 0;
}