Pagini recente » Cod sursa (job #872546) | Cod sursa (job #1951174) | Cod sursa (job #1506484) | Cod sursa (job #2624397) | Cod sursa (job #163665)
Cod sursa(job #163665)
#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