Pagini recente » Cod sursa (job #2589751) | Cod sursa (job #145775) | Cod sursa (job #1225316) | Cod sursa (job #662960) | Cod sursa (job #1150814)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int l=1, heap[100000];
typedef struct {
int a;
int d;
int t;
}oaie;
oaie o[100000];
void urca(int heap[], int poz)
{
while(poz>1 && o[heap[poz]].a > o[heap[poz/2]].a)
{swap(heap[poz], heap[poz/2]);
poz/=2;
}
}
void coboara(int heap[], int &n, int poz)
{
if(2*poz>n) return;
int poz1=2*poz;
if(poz1+1<=n && o[heap[poz1]].a<o[heap[poz1+1]].a)
poz1++;
if(o[heap[poz1]].a > o[heap[poz]].a)
{
swap(heap[poz1], heap[poz]);
coboara(heap, n, poz1);
}
}
void inserare(int heap[], int &n, int val)
{
n++;
heap[n]=l;
urca(heap, n);
l++;
}
void el_varf(int heap[],int &n)
{
heap[1]=heap[n--];
coboara(heap, n, 1);
}
int cmp(oaie x, oaie y) {
return (x.t>y.t);
}
int main()
{
FILE *fin, *fout;
fin=fopen("lupu.in", "r");
fout=fopen("lupu.out", "w");
int maxim, s, n, x, ll, i, j, nr=0;
maxim=0;
s=0;
fscanf(fin, "%d %d %d", &n, &x, &ll);
for(i=1; i<=n; i++)
{
fscanf(fin, "%d %d", &o[i].d, &o[i].a);
o[i].t=(x-o[i].d)/ll+1;
if(o[i].t>maxim)
maxim=o[i].t;
}
sort(o+1, o+n+1, cmp);
/*for(i=1; i<=n; i++)
cout<<o[i].t<<" ";*/
for(i=maxim; i>=1; i--){
while(o[l].t==i) {
inserare(heap, nr, l);
}
s+=o[heap[1]].a;
//cout<<nr<<" "<<o[heap[1]].a<<" ";
el_varf(heap, nr);
}
fprintf(fout, "%d", s);
}