Pagini recente » Cod sursa (job #2025847) | simulare_oji_2023_clasa_9 | Cod sursa (job #149544) | Cod sursa (job #2968664) | Cod sursa (job #24540)
Cod sursa(job #24540)
# include <stdio.h>
# define _fin "lupu.in"
# define _fout "lupu.out"
# define maxn 100002
int n, x, dl, d[maxn], l[maxn], t[maxn];
int a[maxn];
long long sol;
void readf()
{
freopen(_fin, "r", stdin);
int i;
for (scanf("%d%d%d", &n, &x, &dl), i=1; i<=n; i++)
scanf("%d%d", d+i, l+i), t[i] = (x-d[i]) / dl;
}
// HEAP
inline int st(int x) { return x<<1; }
inline int dr(int x) { return (x<<1)|1; }
inline int pr(int x) { return x>>1; }
void reheap(int i)
{
int max;
while ( 1 )
{
max = i;
if ( st(i) <= a[0] && a[st(i)] >= a[max] ) max = st(i);
if ( dr(i) <= a[0] && a[dr(i)] >= a[max] ) max = dr(i);
if ( max==i ) break;
a[i] ^= a[max] ^= a[i] ^= a[max];
i=max;
}
}
void insert(int x)
{
int pos=++a[0];
while ( a[ pr(pos) ] < x && pos > 1 )
a[ pos ] = a[ pr(pos) ], pos = pr(pos);
a[pos] = x;
}
int getmax()
{
if ( !a[0] ) return 0;
int ret = a[1];
a[1] = a[ a[0]-- ];
reheap(1);
return ret;
}
// qs -> sort t + l
int qspoz(int st, int dr)
{
int x=t[st], xl=l[st];
while ( st < dr )
{
while ( st < dr && t[dr] >= x ) dr--;
t[st] = t[dr], l[st] = l[dr];
while ( st < dr && t[st] <= x ) st++;
t[dr] = t[st], l[dr] = l[st];
}
t[st] = x, l[st] = xl;
return st;
}
void qs(int st, int dr)
{
int m = qspoz(st, dr);
if ( st < m ) qs(st, m-1);
if ( m < dr ) qs(m+1, dr);
}
void solve()
{
qs(1, n);
int j, crt=n;
for (j=t[n]; j>=0; j--)
{
// inseram cele cu ti = j
while ( t[crt]>=j && crt>=1 )
insert( l[crt--] );
sol += (long long)getmax();
}
}
void writef()
{
freopen(_fout, "w", stdout);
printf("%lld\n", sol);
}
int main()
{
readf();
solve();
writef();
}