Pagini recente » Cod sursa (job #921161) | Cod sursa (job #1100165) | Cod sursa (job #2557319) | Cod sursa (job #761554) | Cod sursa (job #436507)
Cod sursa(job #436507)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
using namespace std;
FILE *fin,*fout;
int n,h,u;
typedef struct
{
unsigned int height;
unsigned int value;
unsigned int nivel;
}cell;
int initialSort(const void * a, const void * b)
{
cell v1 = *((cell *)a);
cell v2 = *((cell *)b);
if(v1.nivel == v2.nivel) return -(v1.value - v2.value);
return -(v1.height - v2.height);
}
bool permaSort(const int &a, const int &b) {
return a >= b;
}
int main()
{
unsigned int i,poz,nivel,cate,gata_nivel;
cell v[100000];
vector<int> myvector;
vector<int>::iterator it;
fin = fopen("gutui.in","r");
fscanf(fin,"%i %i %i",&n,&h,&u);
for(i=0; i<n; i++)
{
fscanf(fin,"%i %i",&v[i].height,&v[i].value);
v[i].nivel = 1 + (h - v[i].height)/u;
}
fclose(fin);
qsort(v,n,sizeof(cell),initialSort);
/*
for(i=0; i<n; i++)
{
printf("%i %i %i\n",v[i].height,v[i].value,v[i].nivel);
}
*/
for(poz = 0; poz< n; )
{
nivel = v[poz].nivel;
gata_nivel = 0;
// printf("New level: %i ! \n",nivel);
for(i = poz; i< poz + nivel; i++)
{
if(v[i].nivel != nivel)
{
gata_nivel = 1;
break;
}
cate = 0;
// sort (myvector.begin(), myvector.end(),permaSort);
/*
printf("before check :\n");
for (vector<int>::iterator it2 = myvector.begin(); it2 < myvector.end(); it2++)
printf("%i ",*it2);
printf("\n");
*/
for ( it=myvector.begin() ; it < myvector.end(); it++)
{
if (v[i].value <= *it)
{
cate ++;
}
}
if( cate < v[i].nivel )
{
myvector.push_back(v[i].value);
push_heap(myvector.begin(), myvector.end(),permaSort);
}
while(myvector.size() > v[i].nivel)
{
//myvector.erase(myvector.begin());
pop_heap(myvector.begin(), myvector.end(),permaSort);
myvector.pop_back();
}
/*
printf("after check :\n");
for (vector<int>::iterator it2 = myvector.begin(); it2 < myvector.end(); it2++)
printf("%i ",*it2);
printf("\n");
*/
}
if(!gata_nivel)
{
while(v[i].nivel == nivel)
{
i++;
}
}
poz = i;
}
cate = 0;
for ( it=myvector.begin() ; it < myvector.end(); it++ )
{
// printf("%i ",(*it));
cate += (*it);
}
fout = fopen("gutui.out","w");
fprintf(fout,"%i",cate);
fclose(fout);
return 0;
}