Pagini recente » Cod sursa (job #463582) | Cod sursa (job #2641885) | Cod sursa (job #2663843) | Cod sursa (job #463083) | Cod sursa (job #463704)
Cod sursa(job #463704)
//TUDOSE VLAD 323CA - GUTUI
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
//structura in care retin inaltimea,greutatea
//unei gutui si cate gutui mai pot fi culese
//inainte ca inaltimea gutuii sa devina >H
typedef struct{
long weight;
long height;
long lifetime;
}quince;
//functie de comparare a inaltimilor
//folosita la sortare
bool compare (quince i,quince j)
{
return (i.height>j.height);
}
//functie care returneza solutia problemei
long Quinces()
{
long N,H,U,total_weight=0,sum=0,last;
int i;
//CITIREA
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);
q[i].lifetime=(H-q[i].height)/U+1;
total_weight+=q[i].weight;
}
fclose(in);
//daca U este 0 returnam suma greutatilor
//tuturor gutuilor
if(!U)
return total_weight;
sort(q.begin(),q.end(),compare);
//numarul de gutui culese va fi egal cu
//lifetime-ul gutuii cu inaltimea cea mai mica
last=q.back().lifetime;
while((q.size() or pq.size())and last)
{
//daca avem ceva in coada de prioritati
//scoatem afara o gutuie iar greutatea ei
//o adaugam la suma finala
if(pq.size())
{
sum+=pq.top();
pq.pop();
last--;
}
//daca nu,trecem la urmatoarea gutuie
else
{
last=q.back().lifetime;
}
//daca mai avem gutui neparcurse si putem ajunge la ele
//le adaugam in coada de prioritati
while(q.size() and q.back().lifetime>=last)
{
pq.push(q.back().weight);
q.pop_back();
}
}
return sum;
}
int main ()
{
//Scrierea solutiei in fisier
FILE *out=fopen("gutui.out","w");
fprintf(out,"%ld",Quinces());
fclose(out);
return 0;
}