Pagini recente » Cod sursa (job #2512660) | Cod sursa (job #3215250) | Cod sursa (job #438885) | Cod sursa (job #372688) | Cod sursa (job #429983)
Cod sursa(job #429983)
#include<fstream.h>
#include<algorithm>
using namespace std;
struct vector { long long a,b ;} v[100005];
long long n,H,u,k,h[100005],smax;
inline int cmp (const vector &v1, const vector &v2) { return v1.a>=v2.a; }
void afisare ()
{
ofstream g("gutui.out");
g<<smax;
g.close();
}
void urca ()
{
int x=k;
while (x>1 && h[x]<h[x/2])
{
h[x]=(h[x]^h[x/2])^(h[x/2]=h[x]);
x>>=1;
}
}
void coboara ()
{
int x=k,y=1,t;
while (x!=y)
{
x=y;
t=x<<1;
if (t<=k && h[x]>h[t]) y=t;
if (t+1<=k && h[y]>h[t+1]) y=t+1;
h[x]=(h[y]^h[x])^(h[y]=h[x]);
}
}
void dinamic ()
{
int nr,i,max;
for (i=1;i<=n;i++)
{
nr=(H-v[i].a)/u+1;
if (nr>k)
{
k++;
smax+=v[i].b;
h[k]=v[i].b;
urca();
}
else
if (h[1]<v[i].b)
{
smax+=(v[i].b-h[1]);
h[1]=v[i].b;
coboara ();
}
}
}
void citire ()
{
int i;
ifstream f("gutui.in");
f>>n>>H>>u;
for (i=1;i<=n;i++)
f>>v[i].a>>v[i].b;
f.close();
}
int main()
{
citire ();
sort (v+1,v+n+1,cmp);
dinamic ();
afisare ();
return 0;
}