Nu aveti permisiuni pentru a descarca fisierul grader_test3.in

Cod sursa(job #631526)

Utilizator lianaliana tucar liana Data 8 noiembrie 2011 13:38:02
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.08 kb
#include <stdio.h>
#include <set>
#include <algorithm>
#define nmax 100005
using namespace std;
struct fruct{int al,val;};
int n, h, u, sf, i, al, val, minim, poz, sc, rez, x;
multiset <int> a;
fruct v[nmax];
multiset <int>::iterator it;

bool cmp(fruct a, fruct b)
{	return (a.al>b.al);}
	
void citire()
{
	scanf("%ld %ld %ld",&n,&h,&u);
	for (i=1;i<=n;i++)
	{
		scanf("%ld %ld",&al,&val);
		if (al<=h)
		{	v[++sf].al=al;	v[sf].val=val;}
	}
	n=sf;
	sort(v+1,v+1+n,cmp);
}

void rezolvare()
{
	poz=1;
	for (sc=0;h>=sc*u;sc++)
	{
		if ((v[poz].al<=h-sc*u) && (v[poz].al>h-u*(sc+1)))
		{
			a.insert(v[poz].val);	rez+=v[poz].val;
			poz++;
		}
		else
			a.insert(0);
		while ((v[poz].al<=h-sc*u) && (v[poz].al>h-u*(sc+1)) &&(poz<=n))
		{
			it=a.begin();
			minim=*it;
			if (minim<v[poz].val)
			{
				a.erase(a.find(minim));	rez-=minim;
				x=v[poz].val;
				a.insert(x);
				rez+=x;
			}
			poz++;
		}
	}
}

int main()
{
	freopen("gutui.in","r",stdin);
	freopen("gutui.out","w",stdout);
	citire();
	rezolvare();
	printf("%ld",rez);
	return 0;
}