Cod sursa(job #1844743)

Utilizator cochinteleandreeaCochintele Andreea Elena cochinteleandreea Data 10 ianuarie 2017 13:44:25
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>
using namespace std;
int n,gmax,i,s,in,x[5005];
double c[5005];
bool ok;
struct nod
{
    double cost;
    int ind;
}c1[5005],aux;
int main()
{
    cin>>n>>gmax;
    for(i=1;i<=n;i++)
    {
        cin>>x[i]>>c[i];
        c1[i].cost=c[i]/x[i];
        c1[i].ind=x[i];
    }
    do
    {
        ok=true;
        for(i=1;i<n;i++)
        if(c1[i].cost<c1[i+1].cost)
        {aux=c1[i];c1[i]=c1[i+1];c1[i+1]=aux;ok=false;}
    }while(!ok);

    for(i=1;i<=n;i++)
    if(in+c1[i].ind<gmax ) {in+=c1[i].ind;  s+=c1[i].ind*c1[i].cost;}
    else s+= c1[i].cost*(gmax-in),in=gmax;

    cout<<s;
    return 0;
}