Nu aveti permisiuni pentru a descarca fisierul grader_test7.ok
Cod sursa(job #194830)
Utilizator | Data | 14 iunie 2008 18:29:38 | |
---|---|---|---|
Problema | Lupul Urias si Rau | Scor | 16 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.92 kb |
#include<stdio.h>
#include<algorithm>
#define nmax 100024
using namespace std;
typedef struct{
int cost,timp;
}q;
q v[nmax];
inline int cmp(q A,q B) {
return A.timp<B.timp;
}
int h[nmax];
int sf;
int N,X,L;
void change(int a,int b)
{
h[a]^=h[b];
h[b]^=h[a];
h[a]^=h[b];
}
void upp(int poz)
{
if( poz>1 ){
int new_poz=poz>>1;
if( h[new_poz]<h[poz] ){
change(poz,new_poz);
upp(new_poz);
}
}
}
void down(int poz)
{
int left=poz<<1;
int right=poz+1;
int ctrl=poz;
if( left <= sf ){
if( h[left]<=h[poz] )
ctrl=left;
if( right <= sf)
if( h[right]<=h[ctrl] )
ctrl=right;
}
if( ctrl!=poz )
{
change(ctrl,poz);
down(ctrl);
}
}
void show()
{ printf("\n\n");
int i;
printf(" sf= %d\n",sf);
for(i=1; i<=sf; ++i)
printf("%d ",h[i]);
printf("\n");
}
void show_1()
{
int i;
for(i=1; i<=N; ++i)
printf("%d %d\n",v[i].timp,v[i].cost);
printf("\n\n");
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int i,n;
int solfin=0;
int aux1,aux2;
scanf("%d%d%d",&N,&X,&L);
n=0;
for(i=1; i<=N; ++i){
scanf("%d%d",&aux1,&aux2);
if( aux1<=X ){
++n;
aux1=(X-aux1)/L;
v[n].timp=aux1;
v[n].cost=aux2;
}
}
N=n;
sort(v+1,v+N+1,cmp);
int p,poz=1,next;
int Tmax=v[N].timp;
//show_1();
for(i=0; i<=Tmax; ++i){
next=1;
if( v[poz].timp>i ){
next+=v[poz].timp-i;
i=v[poz].timp;
}
//formez heap;
sf=0;
while( v[poz].timp==i )
{
h[++sf]=v[poz].cost;
upp(sf);
++poz;
}
//extrag sol
// show();
while( next )
{
--next;
solfin+=h[1];
change(1,sf);
--sf;
down(1);
}//*/
}
printf("%d\n",solfin);
return 0;
}