Pagini recente » Cod sursa (job #3271383) | Cod sursa (job #2133708) | Cod sursa (job #134656) | Cod sursa (job #2721448) | Cod sursa (job #437914)
Cod sursa(job #437914)
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <queue>
using namespace std;
typedef struct{
long weight;
long height;
}quince;
bool compare (quince i,quince j)
{
return (i.height>j.height);
}
long Quinces()
{
long N,H,U,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);
priority_queue<long> pq;
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;
long pick;
sort(q.begin(),q.end(),compare);
last=q.back().height;
pick=(last/U)*U;
int offset = U - H % U;
if (offset == U) offset = 0;
last = offset - U;
while((!q.empty()or!pq.empty())and last<=H)
{
if(!pq.empty())
{
sum+=pq.top();
pq.pop();
last+=U;
pick+=U;
}
else
{
last=q.back().height;
pick=(last/U)*U;
last += U * max((long)1, (q.back().height - last) / U);
}
while(!q.empty()and q.back().height<=last)//pick+U)
{
pq.push(q.back().weight);
q.pop_back();
}
}
return sum;
}
int main ()
{
FILE *out=fopen("gutui.out","w");
fprintf(out,"%ld",Quinces());
fclose(out);
return 0;
}