Pagini recente » Cod sursa (job #1689962) | Cod sursa (job #3146640) | Cod sursa (job #1142168) | Cod sursa (job #1782874) | Cod sursa (job #24543)
Cod sursa(job #24543)
# include <stdio.h>
# include <stdlib.h>
# define _fin "lupu.in"
# define _fout "lupu.out"
# define maxn 100002
int n, x, dl, l[maxn], t[maxn];
int a[maxn];
long long sol;
void readf()
{
FILE *fin = fopen(_fin, "r");
// freopen(_fin, "r", stdin);
int i, d, j;
char buf[24];
for (fscanf(fin, "%d%d%d\n", &n, &x, &dl), i=1; i<=n; i++)
{
fgets(buf, 23, fin);
for (j=d=0; buf[j] != ' '; j++) d=d*10 + buf[j]-0x30;
for (++j; buf[j] != '\n' && buf[j]; j++) l[i]=l[i]*10 + buf[j]-0x30;
// sscanf(buf, "%d%d", &d, l+i),
t[i] = (x-d) / 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 p = rand() % (dr-st+1)+st;
if ( p!=st )
t[p] ^= t[st] ^= t[p] ^= t[st], l[p] ^= l[st] ^= l[p] ^= l[st];
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();
}