Cod sursa(job #163665)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 22 martie 2008 14:52:55
Problema Peste Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda Finala, Clasa a 9-a Marime 1.94 kb
#include <fstream>
std::ifstream f1("peste.in");
std::ofstream f2("peste.out");

struct elem{
             long p, t;
           }plasa[50010];

void merge(long jos, long mij, long sus);
void mergesort(long jos, long sus);
void qsort1(long jos, long sus);
long pivot1(long jos, long sus);

long total, ttotal, k, n, i, j, suma;

int main()
{
  f1>>n>>k>>ttotal;
  for (i=0; i<n; i++)
    f1>>plasa[i].p>>plasa[i].t;
  qsort1(0, n-1);
  mergesort(0, n-1);
  i=0;
  while (ttotal>plasa[n-1].t)
  {
    while (plasa[i].t>ttotal)
      i++;
    j=i;
    suma=0;
    while ((j<(i+k))&&(j<n))
    {
      suma+=plasa[j].p;
      j++;
    }//while
    total+=(ttotal/plasa[i].t)*suma;
    ttotal%=plasa[i].t;
    i++;
  }//while
  f2<<total;
  return 0;
}//main

void merge(long jos, long mij, long sus)
{
  long i1=jos, i2=mij+1, i=jos, j;
  elem temp[50010];
  while ((i1<=mij)&&(i2<=sus))
  {
    if (plasa[i1].t>plasa[i2].t)
    {
      temp[i++]=plasa[i1];
      i1++;
    }//if
    else
    {
      temp[i++]=plasa[i2];
      i2++;
    }//else
  }//while
  for (j=i1; j<=mij; j++)
    temp[i+j-i1]=plasa[j];
  for (j=i2; j<=sus; j++)
    temp[i+j-i2]=plasa[j];
  for (j=jos; j<=sus; j++)
    plasa[j]=temp[j];
}//merge

void mergesort(long jos, long sus)
{
  long m;
  if (jos<sus)
  {
    m=(jos+sus)/2;
    mergesort(jos, m);
    mergesort(m+1, sus);
    merge(jos, m, sus);
  }//if
}//qsort


long pivot1(long jos, long sus)
{
  long i1=jos, i2=sus;
  elem temp;
  while (i1<i2)
  {
    while ((plasa[i1].p<=plasa[jos].p)&&(i1<=i2))
      i1++;
    while ((plasa[i2].p>plasa[jos].p)&&(i1<=i2))
      i2--;
    if ((plasa[i1].p>plasa[i2].p)&&(i1<i2))
    {
      temp=plasa[i1];
      plasa[i1]=plasa[i2];
      plasa[i2]=temp;
    }//if
  }//while
  temp=plasa[i2];
  plasa[i2]=plasa[jos];
  plasa[jos]=temp;  
  return i2;
}//pivot1

void qsort1(long jos, long sus)
{
  long p;
  if (jos<sus)
  {
    p=pivot1(jos, sus);
    qsort1(jos, p-1);
    qsort1(p+1, sus);
  }//if
}//qsort1