Cod sursa(job #438398)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 10 aprilie 2010 18:37:16
Problema Gutui Scor 40
Compilator cpp Status done
Runda teme_upb Marime 0.76 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

#define g first
#define h second

const int NMAX=100001;

int N,H,U,a[NMAX];

pair<int,int> G[NMAX];

int main()
{
	int i,j;
	ifstream fin("gutui.in");
	fin>>N>>H>>U;
	for (i=1;i<=N;++i) fin>>G[i].h>>G[i].g;

	sort(G+1,G+N+1);
	int na=0;
	for (i=N;i>0;--i)
	{
		vector<int> v;
		for (j=1;j<=na;++j) v.push_back(G[a[j]].h);
		sort(v.rbegin(),v.rend());
		bool ok=true;
		for (j=0;j<(int)v.size();++j)
			if (v[j] < G[i].h) break;
	    for (;j<(int)v.size();++j)
			if (v[j]+ (j+1)*U > H)
			{
				ok=false;
				break;
			}
		if (ok) a[++na]=i;
	}

	int sum=0;
	for (i=1;i<=na;++i) sum+=G[a[i]].g;

	ofstream fout("gutui.out");
	fout<<sum;

	return 0;
}