Cod sursa(job #1707890)

Utilizator acer18Herta Alina acer18 Data 26 mai 2016 01:14:59
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb

#include <fstream>
#include<algorithm>
using namespace std;
 
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
 
struct piatra{
	int val,greu,ind;
};
piatra A[100100];
int N,M;
double Gr,rs;

bool comp(piatra a,piatra b){
	return 1.0*a.val/a.greu > 1.0*b.val/b.greu;
}

void greedy()
{	int i;
    for (i=0,Gr=M;i<N && Gr;++i){
    	fo << A[i].ind << ' ';
		if(Gr >= A[i].greu){
			Gr-=A[i].greu;
			rs+=A[i].val;
			fo << 100 << '\n';	
		} 
    	else{
    		rs+=1.0*Gr*(1.0*A[i].val/A[i].greu);
			fo << (100.0*Gr/A[i].greu);
			Gr = 0;	
		}
	
	}
}
 
 
int main()
{
    int i;
    fi>>N>>M;
    for (i=0;i<N;++i)
    {
        fi>>A[i].val >> A[i].greu;
        A[i].ind = i+1;
    }
    
    sort(A,A+N,comp);
    greedy();
	fo << '\n' << rs;
    return 0;
}