Pagini recente » Cod sursa (job #2158072) | Cod sursa (job #2455816) | Cod sursa (job #876813) | Cod sursa (job #2199967) | Cod sursa (job #2428753)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
struct oaie{
int d,l;
bool operator < (const oaie & aux)const{
return d>aux.d;
}
}auxx;
long long suma=0;
std::ifstream in("lupu.in");
std::ofstream out("lupu.out");
std::vector<oaie>v;
std::priority_queue<int,std::vector<int>,std::greater<int> > pq,pq2;
int main(){
int n,x,l;
bool ok=1;
in>>n>>x>>l;
v.reserve(n+1);
for( register int i=1;i<=n;i++)
in>>auxx.d>>auxx.l,v.push_back(auxx);
std::sort(v.begin(),v.end());
for(register int i=0;i<n;i++){
if(v[i].d+suma<=x)
suma+=l,pq.push(v[i].l),pq2.push(v[i].l);
else{
int cnt=0,last=0;
if(ok)
pq2=pq;
ok=1;
long long sumad=0;
while(!pq2.empty() && v[i].d+suma-cnt*l>x )
sumad+=pq2.top(),pq2.pop(),cnt++;
if(cnt>0 && sumad<=v[i].l &&v[i].d+suma-cnt*l<=x){
suma-=cnt*l;
for(int j=1;j<=cnt;j++)
pq.pop();
pq.push(v[i].l);
suma+=l;
ok=0;
pq2.push(v[i].l);
}
}
}
long long sumax=0;
while(!pq.empty())
sumax+=pq.top(),pq.pop();
out<<sumax;
return 0;
}