Pagini recente » Cod sursa (job #2004434) | Cod sursa (job #232490) | Cod sursa (job #1606223) | Cod sursa (job #1116080) | Cod sursa (job #526633)
Cod sursa(job #526633)
//pana la un timp t adaugam toate solutiile optime care respecta conditia timpului
//ex: toate solutiile pot fi doar din timp 0 spre exemplu
#include <fstream>
#define nmax 100002
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
struct sheep {int dist,lana,timp; } oaie[nmax],heap[nmax]; //timp-numaru de alegeri pana cand oaia nu mai poate fi aleasa
long long sol;
int n,x,l,tmax=-1,heap_size;
void citire ()
{
f>>n>>x>>l;
for (int i=1; i<=n; i++)
{
f>>oaie[i].dist>>oaie[i].lana;
oaie[i].timp=(x-oaie[i].dist)/l;
tmax=max(tmax,oaie[i].timp);
}
f.close ();
}
bool cmp1 (sheep first, sheep second)
{
return first.timp>second.timp;
}
bool cmp2 (sheep first, sheep second)
{
return first.lana<second.lana;
}
void alege_oi ()
{
int i=1;
sort (oaie+1,oaie+n+1,cmp1);
for (int timp=tmax; timp>=0 && i<=n; timp--)
{
while (oaie[i].timp==timp && i<=n)
{
heap[++heap_size]=oaie[i];
push_heap (heap+1,heap+heap_size+1,cmp2);
i++;
}
if (heap_size)
{
sol+=heap[1].lana;
pop_heap (heap+1,heap+heap_size+1,cmp2);
heap_size--;
}
}
}
void afisare ()
{
g<<sol;
g.close ();
}
int main ()
{
citire ();
alege_oi ();
afisare ();
return 0;
}