Pagini recente » Cod sursa (job #2563398) | Cod sursa (job #596674) | Cod sursa (job #376653) | Cod sursa (job #2531878) | Cod sursa (job #2847976)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#define maxi 100005
using namespace std;
long long
ifstream f;
ofstream g;
struct oitza{
long long distanta;
long long cantitate;
};
oitza v[maxi];
priority_queue<pair<long long,long long>> maxheap;
ll n,range,l;
bool cmp(oitza A,oitza B)
{
return(A.distanta<B.distanta);
}
void read()
{
f.open("lupu.in",ios::in);
f>>n>>range>>l;
for(int i=1;i<=n;i++)
{
f>>v[i].distanta>>v[i].cantitate;
}
f.close();
return;
}
long long greedy()
{
long long ans=0;
read();
sort(v+1,v+n+1,cmp);
int cnt=1;
while(v[cnt].distanta<=range&&cnt<=n)
{
maxheap.push(make_pair(v[cnt].cantitate,v[cnt].distanta));
cnt++;
}
long long bonus=0;
while(!maxheap.empty())
{
while(maxheap.top().second+bonus>range&&maxheap.size())
{
maxheap.pop();
}
if(maxheap.size())
{
if(maxheap.top().second+bonus<=range)
{
ans+=maxheap.top().first;
maxheap.pop();
bonus+=l;
}
}
}
return ans;
}
int main()
{
g.open("lupu.out",ios::out);
g<<greedy();
g.close();
return 0;
}