Cod sursa(job #155544)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 11 martie 2008 23:32:49
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>

#include <stdlib.h>
struct ggg
{
   long t,p;
};
typedef struct ggg pozis;
pozis a[2010];

long N,nr;
long S,k,suma[2010],K;

void citire()
{
  freopen ("carnati.in","r",stdin);
  scanf("%ld %ld",&N,&K);
     for (int i=1;i<=N;i++)
	scanf("%ld%ld",&a[i].t,&a[i].p);
  fclose(stdout);
}

void maxim()
{
   long maxim=0;

   for (int i=1;i<=N;i++)
   {
     long S=0,poz=0,ok=0;
     for (int k=1;k<=N;k++)
     {
      if (a[k].p>=a[i].p && ok==0)
      {
	ok=1;
	S=a[i].p;
	poz=a[k].t;
      }
      else
      {
	if (a[k].p>=a[i].p)
	{
	  S+=a[i].p;
	}
      }

       if (S-(a[k].t-poz+1)*K<=0)
       {
	 S=0;
	 ok=0;
	 poz=0;
       }
       else
	 if (S-(a[k].t-poz+1)*K>maxim)
	    maxim=S-(a[k].t-poz+1)*K;
     }
   }
   freopen ("carnati.out","w",stdout);
   printf ("%ld\n",maxim);
   fclose (stdout);
}

void bule ()
{
  int p=N,ok=1;
  while (ok)
  {
    ok=0;
    p--;
    for (int i=1;i<=p;i++)
      if (a[i].t>a[i+1].t)
      {
	pozis aux=a[i];
	a[i]=a[i+1];
	a[i+1]=aux;
	ok=1;
      }
  }
}

int main ()
{
   citire();
   k=0;
//   quick(1,N);
   bule();
   maxim();
   return 0;

}