Cod sursa(job #2102292)

Utilizator osiaccrCristian Osiac osiaccr Data 8 ianuarie 2018 17:03:30
Problema Dosare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <algorithm>
#define DEF 16000
#define INF 1 << 29

using namespace std;

ifstream fin ("dosare.in");
ofstream fout ("dosare.out");

int n, v[DEF], sol[DEF], p, u;

unsigned long long s;

pair < int, int > c[DEF];

int main() {
    fin >> n;
    for (int i = 1; i <= n - 1; ++ i) {
        fin >> v[1];
    }

    for (int i = 1; i <= n; ++ i) {
        fin >> v[i];
        sol[i] = INF;
    }

    c[++ u] = make_pair (1, 1);
    while (p <= u) {
        int nod = c[p].first;
        int cost = c[p].second;

        if (nod + 1 <= n) {
            int temp = nod + 1;
            while (temp % 2 == 0)
                temp /= 2;
            if (temp != 0) {
                if (sol[nod + 1] > cost + 1) {
                    c[++ u] = make_pair (nod + 1, cost + 1);
                    sol[nod + 1] = cost + 1;
                }
            }
            if (2 * nod <= n)
                if (sol[2 * nod] > cost + 1) {
                    c[++ u] = make_pair (2 * nod, cost + 1);
                    sol[2 * nod] = cost + 1;
                }
        }
        ++ p;
    }

    sort (v + 1, v + n + 1);
    sort (sol + 1, sol + n + 1);

    for (int i = 1; i <= n; ++ i) {
        s += v[i] * sol[i];
    }

    fout << s;

    return 0;
}