Cod sursa(job #423462)

Utilizator 2fastGherghina Alexandru 2fast Data 23 martie 2010 21:46:11
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.56 kb
#include <fstream>
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct nod
{
	unsigned int g,h;
	char nr;
	nod *next;
}nod;
	ifstream f("gutui.in");
	ofstream g("gutui.out");
nod *r;
unsigned int n,h,u,l[100000],gr[100000],p[100000],m=0,nr;
void insert()
{
	unsigned int i,j;
	nr=(h-l[0])/u+1;
	nod *p,*q,*e;
	r=new nod;
	r->nr=nr;
	r->g=gr[0];
	r->h=l[0];
	r->next=0;
	//cout<<n<<endl;
	for(i=1;i<n;i++)
	{
		//cout<<"!"<<endl;
		nr=(h-l[i])/u+1;
		if(r->nr>nr || (r->nr==nr && r->g<gr[i]))
		{
			//cout<<"*"<<endl;
			p=new nod;
			p->nr=nr;
			p->g=gr[i];
			p->h=l[i];
			p->next=r;
			r=p;
			//cout<<r->h<<endl;
		}
		else
		{
			//cout<<"**"<<endl;
			p=r;
			while(p!=0)
			{
				q=p;
				p=p->next;
				if(p==0)
				{
					e=new nod;
					e->nr=nr;
					e->g=gr[i];
					e->h=l[i];
					e->next=p;
					q->next=e;
					//cout<<e->h<<endl;
					break;
				}
				if(p->nr>nr || (p->nr==nr && p->g<gr[i]))
				{
					e=new nod;
					e->nr=nr;
					e->g=gr[i];
					e->h=l[i];
					e->next=p;
					q->next=e;
					//cout<<e->h<<endl;
					break;
				}
			}
		}
		//cout<<"!!"<<endl;
	}
	/*
	p=r;
	while(p!=0)
	{
		g<<p->h<<" ";
		p=p->next;
	}*/
}

void parcurg()
{
	nr=1;
	nod *p=r;
	while(p!=0)
	{
		if(p->nr>=nr)
		{
			m+=p->g;
			nr++;
		}
		p=p->next;
	}
	g<<m<<endl;
}

int main()
{
	int i,j;
	f>>n;
	f>>h>>u;
	//memset(p,0,sizeof(int)*100000);
	for(i=0;i<n;i++)
		f>>l[i]>>gr[i];
	insert();
	parcurg();
	f.close();
	g.close();
	return 0;
}