Cod sursa(job #2273859)

Utilizator VintilaMMMVintila Mircea VintilaMMM Data 1 noiembrie 2018 08:11:48
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.75 kb
// https://infoarena.ro/problema/secv3

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

#ifndef DEBUG
//#define DEBUG
#endif // DEBUG

struct ct
{
    unsigned int cost;
    unsigned int timp;
};

bool ctcmp(const ct& a, const ct& b)
{
    return ((double) a.cost / a.timp) > ((double) b.cost / b.timp);
}

int main()
{
    std::ifstream in("secv3.in");
    std::ofstream out("secv3.out");

    unsigned int n;
    unsigned int l; // min sir
    unsigned int u; // max sir

    std::vector<ct> v;

    // citire
    {
        in >> n >> l >> u;

        unsigned int i;
        ct temp = {0, 0};
        v.reserve(n);

        for(i = 0; i < n; i++)
        {
            in >> temp.cost;
            v.push_back(temp);
        }

        for(i = 0; i < n; i++)
            in >> v[i].timp;

        std::sort(v.begin(), v.end(), ctcmp);
    }

    // rezolvare
    unsigned int len = 0;
    auto it = v.begin();
    ct sol = {0, 0};

    while(len < l and it != v.end())
    {
        sol.cost += (*it).cost;
        sol.timp += (*it).timp;
        len++;
        it++;
    }

    while(len < u and ((double) sol.cost / sol.timp) < ((double) (sol.cost + (*it).cost) / (sol.timp + (*it).timp)))
    {
        sol.cost += (*it).cost;
        sol.timp += (*it).timp;
        len++;
        it++;
    }

    out << (double) sol.cost / sol.timp << std::endl;

    #ifdef DEBUG
    std::cout << (double) sol.cost / sol.timp << ' ' << len << std::endl;

    for(auto it = v.begin(); it != v.end(); it++)
        std::cout << (double) (*it).cost / (*it).timp << ' ';
    std::cout << std::endl;
    #endif

    in.close();
    out.close();
    return 0;
}