Cod sursa(job #179216)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 15 aprilie 2008 19:04:51
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream.h>

struct oaie {
	    long long a,b;
	    };

struct nod {
	   long long info;
	   nod *next;
	   };

int poz(oaie v[100001], 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[100001], 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[100001],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[100001];
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;
}