Cod sursa(job #485690)

Utilizator cosmyoPaunel Cosmin cosmyo Data 19 septembrie 2010 10:49:43
Problema Carnati Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include<fstream.h>
#include<algorithm>
const int NMAX=2004;
struct tip{int t;int p;} a[NMAX];
int g,n,c,l[NMAX],maxim=-1000000000;
using namespace std;
int comp(tip x,tip y)
{return x.t<y.t;
}
int main()
{ifstream fin("carnati.in");
 ofstream fout("carnati.out");
	 fin>>n>>c;
	 int i,j;
		 for(i=1;i<=n;++i)
			 fin>>a[i].t>>a[i].p;
 a[0].t=-1000000000;
 sort(a+1,a+n+1,comp);
 for(i=1;i<=n;++i)
	{memset(l,-1000000000,sizeof(l));
		for(j=1;j<=n;++j)
		{ if(a[j].p>=a[i].p)
			  g=a[i].p;
			 else
			  g=0;
		 l[j]=max(l[j-1]-c*(a[j].t-a[j-1].t)+g,g-c);
		if(l[j]>maxim)
			maxim=l[j];
		}
	}
 if(maxim>0)
 fout<<maxim<<'\n';
  else
	  fout<<0<<'\n';
 fin.close();
 fout.close();
 
 return 0;
}