Pagini recente » Cod sursa (job #2533571) | Cod sursa (job #235695) | Cod sursa (job #2301706) | Cod sursa (job #1086596) | Cod sursa (job #87077)
Cod sursa(job #87077)
#include <cstdio>
#include <algorithm>
const int maxn = 100001;
FILE *in = fopen("lupu.in","r"), *out = fopen("lupu.out","w");
struct oaie
{
int D, A;
};
int n, x, l;
oaie a[maxn];
int T[maxn]; // timpul maxim la care oaia i poate fi aleasa
int tkn[maxn]; // 1 daca am ales o oaie la momentul i
bool operator<(const oaie &x, const oaie &y)
{
return x.A > y.A;
}
void read()
{
fscanf(in, "%d %d %d", &n, &x, &l);
for ( int i = 1; i <= n; ++i )
fscanf(in, "%d %d", &a[i].D, &a[i].A);
}
int search(int tmax)
{
int st = 1, dr = n;
int r = 0;
while ( st <= dr )
{
int m = ( st + dr ) >> 1;
if ( m > tmax )
dr = m - 1;
else if ( m <= tmax )
{
st = m + 1;
if ( !tkn[m] )
r = m;
}
// else if ( !tkn[m] )
// return m;
}
return r;
}
int main()
{
read();
std::sort(a+1, a+1+n);
for ( int i = 1; i <= n; ++i )
{
int p = 0;
while ( p + a[i].D <= x )
++T[i], p += l;
}
int answ = 0;
// for ( int i = 1; i <= n; ++i )
// printf("%d %d %d\n", a[i].D, a[i].A, T[i]);
for ( int i = 1; i <= n; ++i )
{
int t = search( T[i] );
//printf("%d\n", t);
if ( t )
answ += a[i].A, tkn[t] = 1;
}
fprintf(out, "%d\n", answ);
return 0;
}