Cod sursa(job #163518)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 22 martie 2008 14:37:00
Problema Peste Scor 20
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 9-a Marime 1.71 kb
#include <stdio.h>
#define MAX 50010

struct lol
{
   int timp,peste;
};

lol a[MAX];
int b[MAX],n,K,Total,k;
lol pes[MAX],nrpeste;

void citire()
{
  freopen ("peste.in","r",stdin);
  scanf ("%d%d%d",&n,&K,&Total);
  for (int i=0;i<n;i++)
  {
    scanf ("%d%d",&a[i].peste,&a[i].timp);
  }
  fclose(stdin);
}

void poz (int li,int ls ,int &k,lol a[MAX] )
{
  int i=li,j=ls,aux,i1=0,j1=-1;
  lol aux1;
  while (i<j)
  {
    if (a[i].timp>a[j].timp)
    {
      aux1=a[i];
      a[i]=a[j];
      a[j]=aux1;
      aux=i1;
      i1=-j1;
      j1=-aux;
    }
    i+=i1;
    j+=j1;
  }
  k=i;
}

void qsort (int li,int ls)
{
  if (li<ls)
  {
    poz(li,ls,k,a);
    qsort(li,k-1);
    qsort(k+1,ls);
  }
}

void poz1 (int li,int ls ,int &k,lol a[MAX] )
{
  int i=li,j=ls,aux,i1=0,j1=-1;
  lol aux1;
  while (i<j)
  {
    if (a[i].peste<a[j].peste)
    {
      aux1=a[i];
      a[i]=a[j];
      a[j]=aux1;
      aux=i1;
      i1=-j1;
      j1=-aux;
    }
    i+=i1;
    j+=j1;
  }
  k=i;
}

void qsort1 (int li,int ls)
{
  if (li<ls)
  {
    poz1 (li,ls,k,pes);
    qsort1 (li,k-1);
    qsort1 (k+1,ls);
  }
}


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

void cauta()
{
  qsort(0,n-1);

  int pozsir=0;
  for (int i=0;i<=Total;i++)
  {
    k=0;
    while (a[pozsir].timp<=i && pozsir<n)
    {
       pes[pozsir++]=a[pozsir];
    }
    qsort1(0,pozsir-1);
    for (int j=0;j<K;j++)
       b[i]+=pes[j].peste;

    for (int y=1;y<=i/2;y++)
       b[i]=max(b[i],b[y]+b[i-y]);
  }
}


int main ()
{
  citire();
  cauta();
  freopen ("peste.out","w",stdout);
  printf ("%d \n",b[Total]);
  fclose (stdout);
  return 0;
}