Cod sursa(job #485691)

Utilizator cosmyoPaunel Cosmin cosmyo Data 19 septembrie 2010 10:52:10
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 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;
 sort(a+1,a+n+1,comp);
 for(i=1;i<=n;++i)
	{memset(l,0,sizeof(l));
	  if(a[1].p>=a[i].p)
        g=a[i].p;
      else
        g=0;
     l[1]=g-c;	  
       for(j=2;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;
}