Pagini recente » Cod sursa (job #247058) | Cod sursa (job #702128) | Cod sursa (job #1871544) | Cod sursa (job #709533) | Cod sursa (job #2102292)
#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;
}