Pagini recente » Cod sursa (job #2834036) | Cod sursa (job #2054942) | Cod sursa (job #3293965) | Cod sursa (job #3201534) | Cod sursa (job #178947)
Cod sursa(job #178947)
#include<fstream.h>
struct oaie {
long long a,b;
};
struct nod {
long long info;
nod *next;
};
int poz(oaie v[100002], int p, int u)
{
oaie piv=v[p],aux;
while (p<u)
{
if (v[p].a>v[u].a || v[p].a==v[u].a && v[p].b<v[u].b) {
aux=v[p];
v[p]=v[u];
v[u]=aux;
}
if (piv.a==v[p].a && piv.b==v[p].b) u--;
else p++;
}
return p;
}
void quick (oaie v[100002], int p, int u)
{
int k;
if (p<u) {
k=poz(v,p,u);
quick(v,p,k-1);
quick(v,k+1,u);
}
}
int cautbin (oaie v[100002],int n, int val)
{
int p=1,i=0;
for (p;p*2<=n;p*=2);
v[0].a=0;
for (;p;p/=2)
if (i+p<=n && (v[p+i].a<val || v[i+p].a==val && v[i+p-1].a==v[i+p].a-1)) i+=p;
return i;
}
int main()
{
int n,i,j,k,l,h=0;
oaie v[100002];
ifstream f("lupu.in");
f>>n>>k>>l;
for (i=1;i<=n;i++)
{
h++;
f>>v[h].a>>v[h].b;
if (v[h].a>k) h--;
else v[h].a=(k-v[h].a)/l+1;
}
f.close();
n=h;
quick(v,1,n);
nod *p,*u,*q,*t;
p=0;p=new nod;p->info=v[1].b;p->next=0;u=p;
int ord=2,poz,sw;
while (ord<=k/l+1)
{
poz=cautbin(v,n,ord);
for (i=poz;i<=poz+ord-1 && v[i].a==ord && i<=n; i++)
{
t=new nod;
t->info=v[i].b;
if (t->info>p->info) {
t->next=p;
p=t;
}
else if (t->info<u->info) {u->next=t;t->next=0;u=t;}
else {
q=p; sw=1;
while (q->next && sw)
{
if (t->info>q->next->info) {sw=0;t->next=q->next;q->next=t;
}
q=q->next;
}
}
}
h=0;
for (q=p;q && h<ord-1;q=q->next, h++);
u=q;u->next=0;
ord++;
}
long long s=0;
while (p)
{
s+=p->info;
p=p->next;
}
ofstream g("lupu.out");
g<<s; g.close();
return 0;
}