Panic at the power plant

The research and development center of the enemy country, Ostania, has come up with a new power generation technique. For this they have employed a huge number of machines in a huge room as an array of machines. Your country's best spy, Twilight, has found out that the generated power of the whole system is the sum of all the generated power of each machine.

However, the problem is that the power generated by each machine is not same for every machine. More specifically, the power generated by each machine is dependant on the position of the machine and two parameters each have; trimpet and trumput. Twilight has discovered that the power generated by each machine is the product of trimpet and number of machines before it added to the product of trumput and the number of machines after it. He has sent all these information and the parameter values of each machine to you. However, he has not been able to find the actual order of the machines.

As an intelligence officer, you have to estimate the maximum power that they can generate so that the higher officials can get a better understanding of the situtation.

Input Format

First line, n contains the number of machines. Next n lines denote the the trimpet and trumput paramters of each machine.

Constraints

Output Format

Output a single number containing the maximum performance possible.

Sample Input 0

3
6 7
3 9
8 6

Sample Output 0

47

Explanation 0

The order that maximizes performance is first machine at the middle with second machine at the front and last machine at end. (order 2 1 3)

The performance of first machine is 6 + 7 = 13.

The performance of second machine is 9*2 = 18.

The performance of third machine is 8*2 = 16.

So the maximum performance is 13 + 18 + 16 = 47.

Solution

Algorithm by Kalana Abeysundara

Code by Suhas Dissanayake

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

bool cmp(const vector<int>& a, const vector<int>& b){
    return a[0] < b[0];
}

int main() {
    int n;
    cin >> n;
    int j = n;

    vector<vector<int>> items;

    while(j--){
        int a, b;
        cin >> a >> b;
        vector<int> item = {a-b, a, b};
        items.push_back(item);
    }

    sort(items.begin(),items.end(),cmp);

    long long sum = 0;
    int size = items.size();

    for(int i = 0; i < size; i++){
        auto item = items[i];
        sum += item[1] * i + item[2] * (size - 1 - i);
    }

    cout << sum << endl;

    return 0;
}