KOPC12A

KOPC12A - K12 - Building Construction

#include <iostream>

#include <cmath>

#define REP(i, n) for(int i = 0; i < n; i++)

using namespace std;

const int N = 10005;

int height[N];

int cost[N];

int n;

//finds the total cost for height h

long long int findCost(int h)

{

    long long c = 0; //cost

    REP(i, n)

    {

        c += abs(h - height[i]) * cost[i];

    }

    return c;

}

int ternary_search(int l, int h)

{

    while(l <= h)

    {

        if(l == h)

            break;

        int mid1 = l + (h - l) / 3;

        int mid2 = h - (h - l) / 3;

        if(findCost(mid1) > findCost(mid2))

            l = mid1 + 1;

        else

            h = mid2 - 1;

    }

    return l;

}

int main()

{

    int t, maxHeight;

    cin >> t;

    while(t--)

    {

        cin >> n;

        maxHeight = 0;

        REP(i, n)

        {

            cin >> height[i];

            if(height[i] > maxHeight)

                maxHeight = height[i];

        }

        REP(i, n)

        {

            cin >> cost[i];

        }

        int h = ternary_search(0, maxHeight);

        cout << findCost(h) << endl;

    }

    return 0;

}