Pagini recente » Cod sursa (job #341875) | Cod sursa (job #2886140) | Rating ruxandra craciunescu (ruxy) | Cod sursa (job #1707869) | Cod sursa (job #1976581)
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
FILE *f, *g;
int n, mx, l;
int h[100009];
int nod;
struct oaia
{
int d, c;
};
oaia v[100009];
void readFile()
{
f = fopen("lupu.in", "r");
fscanf(f, "%d%d%d", &n, &mx, &l);
int i, a, b;
for(i = 1; i <= n; i ++)
{
fscanf(f, "%d%d", &v[i].d, &v[i].c);
}
fclose(f);
}
bool cmp(oaia a, oaia b)
{
return a.d > b.d;
}
void ins(int i, int nr)
{
nod ++;
h[nod] = i;
}
void sch(int &a, int &b)
{
int aux = a;
a = b;
b = aux;
}
void downHeap(int poz)
{
int fiu = poz;
while(poz * 2 <= nod)
{
fiu = poz;
if(poz * 2 <= nod && h[poz * 2] < h[fiu])
fiu = poz * 2;
if(poz * 2 + 1 <= nod && h[poz * 2 + 1] < h[fiu])
fiu = poz * 2 + 1;
if(fiu != poz)
{
sch(h[fiu], h[poz]);
poz = fiu;
}
}
}
void upHeap(int poz)
{
while(poz > 1 && h[poz] < h[poz / 2])
{
//printf("%d %d %d\n", poz, h[poz], h[poz / 2]);
sch(h[poz], h[poz / 2]);
poz /= 2;
}
}
void del()
{
h[1] = 0;
sch(h[1], h[nod]);
nod --;
downHeap(1);
}
void ins(int poz)
{
nod ++;
h[nod] = poz;
upHeap(nod);
}
long long rez;
void solve()
{
sort(v + 1, v + n + 1, cmp);
int i = 1;
while(i <= n && v[i].d > mx)
i ++;
for(; i <= n; i ++)
{
// printf("Suntem pe %d %d %d", i, v[i].d, v[i].c);
if(v[i].d <= mx)
{
// printf("****");
ins(v[i].c);
rez += v[i].c;
mx -= l;
}
else
{
if(nod > 0 && v[i].c > h[1])
{
// printf("*");
rez -= h[1];
rez += v[i].c;
del();
ins(v[i].c);
}
}
// printf("\n");
// printf(" %d\n", h[1]);
// printf("%d %d\n\n", h[2], h[3]);
// printf("%d ")
}
}
void printFile()
{
g = fopen("lupu.out", "w");
fprintf(g, "%lld\n", rez);
fclose(g);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}