Cod sursa(job #439206)

Utilizator 2fastGherghina Alexandru 2fast Data 11 aprilie 2010 14:05:03
Problema Gutui Scor 70
Compilator cpp Status done
Runda teme_upb Marime 1.73 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;

void print_list(nod *r)
{
	nod *p;
	p=r->next;
	while(p!=0)
	{
		cout<<p->gr<<" ";
		p=p->next;
	}
	system("pause");
}

void insert_nr(nod *r,int nr,int gr)
{
	unsigned int i;
	nod *p,*q,*e;
	q=r;
	p=r->next;
	int ok=0;
	while(p!=0)
	{
		if(p->nr>nr || (p->nr==nr && p->gr<gr))
		{
			e=new nod;
			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->nr=nr;
		p->gr=gr;
		p->next=0;
		q->next=p;
	}
}

void insert_gr(nod *r,int nr,int gr)
{
	unsigned int i;
	nod *p,*q,*e;
	q=r;
	p=r->next;
	int ok=0;
	while(p!=0)
	{
		if(p->gr>gr)
		{
			e=new nod;
			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->nr=nr;
		p->gr=gr;
		p->next=0;
		q->next=p;
	}
}

int main()
{
	f>>n;
	f>>h>>u;
	nod *r=new nod;
	nod *s=new nod;
	nod *q;
	r->next=0;
	s->next=0;
	int i,nr;
	for(i=0;i<n;i++)
	{
		f>>l>>gr;
		nr=(h-l)/u+1;
		insert_nr(r,nr,gr);
	}
	//print_list(r);
	nod *p=r->next;
	unsigned int ut=0;
	while(p!=0)
	{
		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);
			}
		p=p->next;
	}
	p=s->next;
	unsigned int max=0;
	while(p!=0)
	{
		max+=p->gr;
		p=p->next;
	}
	g<<max<<endl;
	//print_list(s);
	f.close();
	g.close();
	return 0;
}