Pagini recente » Cod sursa (job #1291852) | Cod sursa (job #3204544) | Cod sursa (job #2007382) | Cod sursa (job #1124779) | Cod sursa (job #437814)
Cod sursa(job #437814)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <vector>
#define max(a,b) (a)<(b)?(b):(a)
using namespace std;
typedef struct{
long weight;
long height;
}quince;
bool compare (quince i,quince j)
{
return (i.height>j.height);
}
long gutui()
{
long N,H,U,left,total_weight=0,sum=0,last;
int i;
FILE *in=fopen("gutui.in","r");
fscanf(in,"%ld %ld %ld\n",&N,&H,&U);
vector<quince> q (N);
vector<long> heap;
make_heap(heap.begin(),heap.end());
for(i=0;i<N;i++)
{
fscanf(in,"%ld %ld\n",&q[i].height,&q[i].weight);
total_weight+=q[i].weight;
}
fclose(in);
if(!U)
return total_weight;
sort(q.begin(),q.end(),compare);
last=q.back().height;
while((!q.empty()||heap.size())&&last<=H)
{
if(heap.size())
{
sum+=heap.front();
pop_heap(heap.begin(),heap.end());
heap.pop_back();
last+=U;
}
else
last=q.back().height;
while(!q.empty())
{
if(q.back().height>last+U)
break;
heap.push_back(q.back().weight);
push_heap(heap.begin(),heap.end());
q.pop_back();
}
}
return sum;
}
int main ()
{
FILE *out=fopen("gutui.out","w");
fprintf(out,"%ld",gutui());
fclose(out);
return 0;
}