Pagini recente » Cod sursa (job #2282208) | Cod sursa (job #1492396) | Cod sursa (job #2721875) | Cod sursa (job #1050741) | Cod sursa (job #1633907)
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
const int NMAX=100005;
struct Pct{
long long init,cost,poz;
};
struct cmp{
inline bool operator ()(const Pct A,const Pct B)
{
return A.cost<=B.cost;
}
};
inline bool cmp1 (const Pct A, const Pct B)
{
return A.init>=B.init;
}
Pct a[NMAX];
bool viz[NMAX];
priority_queue <Pct,vector <Pct>,cmp > Q;
int main()
{
int n,x,d;
f>>n>>x>>d;
for(int i=1;i<=n;i++)
{
f>>a[i].init>>a[i].cost;
a[i].poz=i;
}
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)
Q.push(a[i]);
long long sol=0;
int cnt=0;
bool ok=0;
/*for(int i=1;i<=n;i++)
{
int j=i+1;
if(j>=n)
break;
if(a[i].init<=x && viz[a[i].init]==0 && ok==0)
{
Q.push(a[i].cost);
if(a[i].init==a[j].init && viz[a[i].init]==0)
{
while(a[i].init==a[j].init)
{
Q.push(a[j].cost);
j++;
}
i=j-1;
}
if(!Q.empty())
{
ok=1;
sol+=Q.top();
cnt++;
}
while(!Q.empty())
Q.pop();
viz[a[i].init]=1;
}
else
if(ok==1)
{
if(a[i].init+1LL*cnt*d<=x && viz[a[i].init]==0)
{
Q.push(a[i].cost);
if(a[i].init==a[j].init && viz[a[i].init]==0)
{
//g<<i<<" "<<j<<"\n";
while(a[i].init==a[j].init)
{
//g<<a[j].cost<<"\n";
Q.push(a[j].cost);
j++;
}
i=j-1;
//g<<"new\n";
//g<<i<<"\n";
}
if(!Q.empty())
{
//g<<Q.top()<<"\n";
sol+=Q.top();
cnt++;
}
while(!Q.empty())
Q.pop();
viz[a[i].init]=1;
}
}
}*/
while(!Q.empty())
{
if(Q.top().init>x)
{
Q.pop();
continue;
}
if(Q.top().init<=x && ok==0)
{
ok=1;
sol+=Q.top().cost;
cnt++;
Q.pop();
}
else
{
if(ok==1)
{
if(Q.top().init+1LL*cnt*d<=x)
{
sol+=Q.top().cost;
cnt++;
Q.pop();
}
else
Q.pop();
}
}
}
g<<sol<<"\n";
return 0;
}