Cod sursa(job #802281)

Utilizator penultim_oVijiala Tudor Gabriel penultim_o Data 26 octombrie 2012 11:36:54
Problema Energii Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

ifstream in("energii.in");
ofstream out("energii.out");

const int INF = 0x4FFFF;
int G, W;
struct gen
{
	int e, c;
	float rap;
} v[1100];

void read()
{
	in >> G >> W ;
	int i, e, c;
	for(i=0; i<G; i++)
	{
		in >> e >> c;
		v[i].e = e; 
		v[i].c = c; 
		v[i].rap = (float)e/c;
	}
}

int comp(gen a, gen b)
{
	return a.rap > b.rap;
}

int main()
{
	read();
	sort(v, v+G, comp);
	
	int i, c=0, e=0;

	for(i=0; e<W && i<G; i++)
	{
		e+=v[i].e;
		c+=v[i].c;
	}
	if(e<W) out << -1;
		else out << c;
	return 0;
}