Pagini recente » Borderou de evaluare (job #2731185) | Borderou de evaluare (job #1523003) | Cod sursa (job #1967696) | Cod sursa (job #2603461) | Cod sursa (job #568257)
Cod sursa(job #568257)
#include<fstream>
#include<stdlib.h>
using namespace std;
struct valeu
{
int gr;
int nivel;
};
int aleluia(const void* x,const void* y)
{
valeu t,u;
t = *((valeu*)x);
u = *((valeu*)y);
return u.gr-t.gr;
}
int main()
{
int poz[100000]={0},n,h,u,i,s,x[10000][10000],max1,a,b,j,z,max,k,y,aux,q,max2;
valeu v[100000];
int count[100000];
ifstream f("gutui.in");
f>>n>>h>>u;
s=0;
z=0;
max1=0;
for(i=0;i<n;i++)
{
f>>a>>b;
if(a<h) x[(h-a)/u][poz[(h-a)/u]]=b;
poz[(h-a)/u]++;
if((h-a)/u>max1) max1=(h-a)/u;
}
f.close();
for(i=0;i<=max1;i++)
{
for(j=0;j<=i&&j<poz[i];j++)
{
max=x[i][j];
k=0;
for(y=j+1;y<poz[i];y++)
{
if(x[i][y]>max) {max=x[i][y]; k=y;}
}
if(k>0) {aux=x[i][j]; x[i][j]=max; x[i][k]=aux;}
}
}
/* de aici avem piramida de maximi pt fiecare nivel*/
q=0;
max2=0;
for(i=0;i<=max1;i++)
for(j=0;j<=i&&j<poz[i];j++)
{
v[q].gr=x[i][j];
v[q++].nivel=i;
max2++;
}
/* qsort pe sir v */
qsort(v,max2,sizeof(valeu),aleluia);
q=0;
for(i=0;i<n&&q<max2;i++)
{
if(v[i].nivel>=count[v[i].nivel])
{
q++;
s+=v[i].gr;
for(j=v[i].nivel;j<max2;j++)
{
count[j]++;
}
}
}
ofstream g("gutui.out");
g<<s;
g.close();
}