Pagini recente » Cod sursa (job #376560) | Cod sursa (job #378580) | Cod sursa (job #2174059) | Cod sursa (job #622711) | Cod sursa (job #2847942)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#define maxi 100005
using namespace std;
using ll=long long;
ifstream f;
ofstream g;
struct oitza{
ll distanta;
ll cantitate;
};
oitza v[maxi];
priority_queue<pair<ll,ll>> 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;
}
ll greedy()
{
ll 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++;
}
ll bonus=0;
while(!maxheap.empty())
{
while(maxheap.top().second+bonus>range&&maxheap.size())
{
maxheap.pop();
}
if(maxheap.size())
{
ans+=maxheap.top().first;
maxheap.pop();
bonus+=l;
}
}
return ans;
}
int main()
{
g.open("lupu.out",ios::out);
g<<greedy();
g.close();
return 0;
}