Pagini recente » Cod sursa (job #2650711) | Cod sursa (job #245452) | Cod sursa (job #1469214) | Cod sursa (job #531555) | Cod sursa (job #441542)
Cod sursa(job #441542)
#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;
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);
}
qsort(v,n,sizeof(gutuie),f);
int j=0;
for(int k=v[0].alt;k>=1;k--)
{
while (v[j].alt == k && j<n)
{
hip.push_back(v[j].val);
push_heap(hip.begin(),hip.end());
j++;
}
if(!hip.empty())
{
pop_heap(hip.begin(),hip.end());
sol+=hip.back();
hip.pop_back();
}
}
fprintf(fout,"%i",sol);
fclose(fin);
fclose(fout);
}