Pagini recente » Cod sursa (job #557776) | Cod sursa (job #1412413) | Cod sursa (job #2057464) | Cod sursa (job #1971276) | Cod sursa (job #1244870)
#include<queue>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int i,j,k,m,n,u,weight;
long long sol;
struct gutui
{
gutui(int x, int y): x1(x), y1(y){}
int x1;
int y1;
};
int x,y;
struct gutui1
{
int r;
int l;
};
gutui1 a[100005];
int height;
bool operator>(const gutui &o1, const gutui &o2)
{
long long h1=(height-o1.x1)/u;
long long h2=(height-o2.x1)/u;
if (h1==h2)
{
return o1.y1>o2.y1;
}
return o1.x1<o2.x1;
}
bool cmp(gutui1 o1, gutui1 o2)
{
if (o1.r==o2.r) return o1.l>o2.l;
else return o1.r>o2.r;
}
int main()
{
freopen("gutui.in","r",stdin);
freopen("gutui.out","w",stdout);
scanf("%d%d%d",&n,&height,&u);
for (i=1; i<=n; ++i) scanf("%d%d",&a[i].r,&a[i].l);
priority_queue<gutui, vector<gutui> , greater<gutui> >q;
sort(a+1,a+n+1,cmp);
//for (i=1; i<=n; ++i) printf("%d %d\n",a[i].r,a[i].l);
for (i=1; i<=n; ++i)
{
if (a[i].r<=height) q.push(gutui(a[i].r,a[i].l));
}
bool ok=true;
int nivel=0;
i=0;
while (ok)
{
++i;
gutui r=q.top();
//printf("%d %d\n",r.x1,r.y1);
if (r.x1+nivel<=height)
{
sol+=r.y1;
q.pop();
nivel+=u;
}
else
{
q.pop();
}
if (i>n || q.empty()) ok=false;
}
printf("%lld\n",sol);
return 0;
}