Cod sursa(job #210131)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 26 septembrie 2008 18:16:33
Problema Carnati Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <stdio.h>      
     
#define FIN "carnati.in"      
#define FOUT "carnati.out"      
#define NMAX 3000
     
struct abc
{
  int timp,pret;
}
v[NMAX];

int N;
long int X,Y,C;
int i,j;
long long smax;
long int poz,s;
long int G;
long int A[2*NMAX];
long long REZ=0;

long int max(long int a, long int b)
{
    if (a>b)
	return a;
	else
	return b;
}

long int min(long int a, long int b)
{
    if (a>b)
	return b;
	else
	return a;
}

void read_data()
{
   freopen(FIN,"rt",stdin);
   scanf("%d %ld", &N, &C);
   for (i=1;i<=N;++i)
	 scanf("%d %ld", &v[i].timp, &v[i].pret);
}      
     
void solve()      
{      
/* for(i=1;i<=N;++i)
      {
      X=0;
      for(j=1;j<=N;++j)
	  {
	  if(v[j].pret>=v[i].pret) G=v[i].pret;
			      else G=0;
	  Y=X-(v[j].timp-v[j-1].timp)*C+G;
	  Y=max(Y,G-C);
	  REZ=max(REZ,Y);
	  X=Y;
	  }
      }    */
      /*for (i=1;i<=N;++i)
	   {
	   for (j=i;j<=N;++j)
		{
		if (v[j].pret>=v[i].pret)
		    G=v[i].pret;
		    else
		    G=0;
		A[2*i]=G-C;
		A[2*i+1]=-(v[i].timp-v[i].timp)*C;
		}
		 }*/
for (i=1;i<=N;++i)
    {
    suma=0;
    X=1;
    smax=max(smax,v[i].pret-C);
    for (j=1;j<=N;++j)
	 {
	 if (v[j].pret>=v[i].pret)
	     suma+=v[i].pret;
	     smax=max(smax,suma-(v[j].timp-v[X].timp+1)*C);
	 if(suma-(v[j].timp-v[X].timp+1)*C<0)
	    suma=0,X=j+1;

		}
	}
}

void write_data()
{
    freopen(FOUT,"wt",stdout);
  //  for (i=1;i<=2*N;++i)
   // printf("%ld ", A[i]);
   // printf("\n");
/*int smax,sum;
int dr,st;
for (smax=A[1],st=1;st<=2*N;++st)
     for (sum=0,dr=st;dr<=2*N;++dr)
      {
       sum+=A[dr];
       if (sum>smax) smax=sum;
       }*/
printf("%lld", smax);
}

int main()
{
    read_data();      
    solve();      
    write_data();      
return 0;
}