Cod sursa(job #439439)

Utilizator 2fastGherghina Alexandru 2fast Data 11 aprilie 2010 16:12:21
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.42 kb
#include <fstream>
#include <iostream>
#include <stdlib.h>
using namespace std;

typedef struct nod
{
	unsigned int gr,nr;
	nod *next;
}nod;

ifstream f("gutui.in");
ofstream g("gutui.out");
unsigned int n,h,u,l,gr,m,nr;

int compare (const void * a, const void * b)
{
  return ( ((nod*)a)->nr - ((nod*)b)->nr );
}

void printv(nod v[])
{
	int i;
	for(i=0;i<n;i++)
		cout<<v[i].gr<<" ";
	cout<<endl;
	system("pause");
}

void insert_gr(nod *r,int nr,int gr)
{
	nod *p,*q,*e;
	q=r;
	p=r->next;
	int ok=0;
	while(p!=0)
	{
		if(p->gr>gr)
		{
			e=new nod;
			//e->x=0;
			e->nr=nr;
			e->gr=gr;
			e->next=p;
			q->next=e;
			ok=1;
			break;
		}
		q=p;
		p=p->next;
	}
	if(!ok)
	{
		p=new nod;
		//p->x=0;
		p->nr=nr;
		p->gr=gr;
		p->next=0;
		q->next=p;
	}
}

int main()
{
	f>>n;
	f>>h>>u;
	int i;
	nod v[n];
	for(i=0;i<n;i++)
	{
		f>>l>>gr;
		v[i].gr=gr;
		v[i].nr=(h-l)/u+1;
	}
	qsort(v,n,sizeof(nod),compare);
	//printv(v);	
	nod *s=new nod;
	nod *q;
	unsigned int ut=0;
	s->next=0;
	for(i=0;i<n;i++)
	{
		nod p;
		p=v[i];
		if(p.nr>ut)
		{
			insert_gr(s,p.nr,p.gr);
			ut++;
		}
		else
			if(s->next->gr<p.gr)
			{
				q=s->next;
				s->next=q->next;
				delete(q);
				insert_gr(s,p.nr,p.gr);
			}
	}
	unsigned int max=0;
	nod *p;
		p=s->next;
	while(p!=0)
	{
		max+=p->gr;
		p=p->next;
	}
	g<<max<<endl;
	f.close();
	g.close();
	return 0;
}