Pagini recente » Cod sursa (job #749633) | Cod sursa (job #2526757) | Cod sursa (job #542596) | Cod sursa (job #301035) | Cod sursa (job #1411659)
#include<stdio.h>
#include<algorithm>
#define MAXN 100005
FILE *f=fopen("lupu.in","r"), *g=fopen("lupu.out","w");
using namespace std;
struct Oite{ int d, l; } v[MAXN]; // dati si lana
int N, Lup, Crestere, HP[MAXN], LHP;
long long R = 0;
bool cmp( Oite A, Oite B ){
if( A.d > B.d || ( A.d == B.d && A.l > B.l ) )
return 1;
return 0;
}
void Citire(){
int i, dist, lana;
fscanf(f,"%d %d %d\n",&N,&Lup,&Crestere);
for(i=1;i<=N;i++){
fscanf(f,"%d %d\n",&dist,&lana);
if( dist <= Lup )
v[i].d = ( Lup - dist ) / Crestere + 1;
else v[i].d = 0;
v[i].l = lana;
}
}
void Pune( int nr ){
int poz;
HP[++LHP] = nr;
poz = LHP;
while( poz > 1 && HP[poz/2] < HP[poz] ){
swap( HP[poz], HP[poz/2] );
poz /= 2;
}
}
void Scoate(){
int poz, mx, pmx;
R += 1LL * HP[1];
if( LHP > 1 )
HP[1] = HP[LHP];
LHP--;
poz = 1;
while(1){
if( poz*2 > LHP )
break;
mx = HP[poz*2];
pmx = poz*2;
if( poz*2+1 <= LHP && HP[poz*2+1] > mx ){
mx = HP[poz*2+1];
pmx = poz*2+1;
}
if( HP[poz] < mx ){
swap( HP[poz], HP[pmx] );
poz = pmx;
}
else
break;
}
}
void Rezolva(){
int ind, zi, zimax = v[1].d;
ind = 1;
for( zi = zimax; zi >= 1; zi -- ){
while( v[ind].d == zi )
Pune( v[ind++].l );
if( LHP > 0 )
Scoate();
} fprintf(g,"%lld\n",R);
}
int main(){
Citire();
sort(v+1,v+N+1,cmp);
Rezolva();
return 0;
}