Pagini recente » Cod sursa (job #1506937) | Cod sursa (job #590640) | Istoria paginii utilizator/valentina.88 | Cod sursa (job #2214064) | Cod sursa (job #441479)
Cod sursa(job #441479)
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> hip;
vector<int>::iterator it;
FILE *fin,*fout;
int n,u,h;
int hm[100000];
typedef struct {int val,alt;}gutuie;
gutuie v[100000];
int f(const void *a,const void *b)
{
gutuie x,y;
x=(*(gutuie *)a);
y=(*(gutuie *)b);
if(x.alt > y.alt)return -1;
if(x.alt < y.alt)return 1;
else
{
if( x.val > y.val)return -1;
return 1;
}
}
int Hmax(int x)
{
int k=0,j=h-x;
if(j<0)return j;
else while(j-u>0){j-=u;k++;}
return k+1;
}
int main()
{
fin=fopen("gutui.in","rt");
fout=fopen("gutui.out","wt");
int sol=0;
fscanf(fin,"%i %i %i",&n,&h,&u);
for(int i=0;i<n;i++)
{
fscanf(fin,"%i %i",&v[i].alt,&v[i].val);
v[i].alt=Hmax(v[i].alt);
// fprintf(fout,"%i %i, ",v[i].alt,v[i].val);
}
qsort(v,n,sizeof(gutuie),f);
// for(int i=0;i<n;i++)
//fprintf(fout,"%i %i, ",v[i].alt,v[i].val);
int j=0;
for(int k=v[0].alt;k>=0;k--)
{ while (v[j].alt == k && j<n)
{
// fprintf(fout,"\n %i",v[j].val);
hip.push_back(v[j].val);
push_heap(hip.begin(),hip.end());
j++;
}
//fprintf(fout,"\n");
//j--;
if(!hip.empty()){pop_heap(hip.begin(),hip.end());sol+=hip.back(); hip.pop_back();}
}
fprintf(fout,"%i",sol);
//for(int i=0;i<n;i++)
//fprintf(fout,"%i %i, ",v[i].alt,v[i].val);
fclose(fin);
fclose(fout);
}