Pagini recente » Cod sursa (job #3203826) | Cod sursa (job #2961254) | Cod sursa (job #1376428)
#include<fstream>
#include<algorithm>
#include<vector>
#define NMAX 100001
using namespace std;
struct SHEEP{int wool, time;};
struct HEAP
{
vector<int> heap;
HEAP()
{
heap.push_back(0);
}
void upHeap(int pos)
{
int val=heap[pos];
int father=pos/2;
while(father && heap[father]<val)
{
heap[pos]=heap[father];
pos=father;
father=pos/2;
}
heap[pos]=val;
}
void push(int val)
{
heap.push_back(val);
upHeap(heap.size()-1);
}
void downHeap(int pos)
{
int son=pos*2;
int val=heap[pos];
while(son<=(heap.size()-1))
{
if(son<(heap.size()-1))
if(heap[son+1]>heap[son])
son++;
if(heap[son]>val)
break;
heap[pos]=heap[son];
pos=son;
son=pos*2;
}
heap[pos]=val;
}
int pop_max()
{
int val=heap[1];
heap[1]=heap.back();
heap.pop_back();
downHeap(1);
return val;
}
};
bool compSHEEP(SHEEP a, SHEEP b)
{
if(a.time<b.time)
return 1;
return 0;
}
SHEEP shp[NMAX];
int main()
{
int n, x, l;
int i;
int initial_distance;
long long total=0;
int nsh;
int tmax=0;
HEAP h;
ifstream f("lupu.in");
f>>n>>x>>l;
for(i=1; i<=n ;i++)
{
f>>initial_distance>>shp[i].wool;
shp[i].time=(x-initial_distance)/l;
if(shp[i].time>tmax)
tmax=shp[i].time;
}
f.close();
sort(shp+1, shp+n+1, compSHEEP);
nsh=n;
for(i=tmax; i>=0; i--)
{
while(shp[nsh].time==i && nsh)
{
h.push(shp[nsh].wool);
nsh--;
}
total=total+(long long)h.pop_max();
}
ofstream g("lupu.out");
g<<total<<'\n';
g.close();
return 0;
}