Editorial

Consider the case of arrays with two elements. Let $A=\{p,q\}(p<q)$ and $B=\{x,y\}$. Let's examine the condition under which the sum $p\cdot x+q\cdot y$ will be minimized. Let's consider two permutation options:

The inequality $p\cdot x+q\cdot y<p\cdot y+q\cdot x$ holds if

Given that $p\ne q$, dividing the inequality by $(p-q)<0$, we obtain $x>y$. This means that the sum $p\cdot x+q\cdot y$ (when $p<q$) will be minimized if $x>y$.

Consider a pair of elements from the original arrays $A$ and $B$. If $a_i<a_j$ and $b_i<b_j$, then by swapping $b_i$ and $b_j$, we decrease the total sum.

Sort array $a$ in ascending order and array $b$ in descending order. Then we'll obtain the sum with the smallest value

Example

Compute the sum for the given example.

Let's take a pair where $a_1<a_5$ and $b_1<b_5$. Swapping $b_1$ and $b_5$ will decrease the sum.

For the given example, for any pair $(i,j)$, if $a_i<a_j$, then $b_i>b_j$. Therefore, the current permutation is optimal.

Let’s consider obtaining the minimum sum by sorting array $a$ in ascending order and array $b$ in descending order.

Algorithm realization

Declare the input arrays.

#define MAX 101
int a[MAX], b[MAX];

Read the input data.

scanf("%d",&n);
for(i = 0; i < n; i++)
  scanf("%d",&a[i]);
for(i = 0; i < n; i++)
  scanf("%d",&b[i]);

Sort the first array in ascending order, and the second array in descending order.

sort(a,a+n);
sort(b,b+n,greater<int>());

Compute the desired minimum sum, which can be a $64$-bit integer.

res = 0;
for(i = 0; i < n; i++)
  res += 1LL * a[i] * b[i];

Print the answer.

printf("%lld\n",res);

Java realization

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    Integer a[] = new Integer[n];
    for(int i = 0; i < n; i++)
      a[i] = con.nextInt();
    
    Integer b[] = new Integer[n];
    for(int i = 0; i < n; i++)
      b[i] = con.nextInt();
    
    Arrays.sort(a);
    Arrays.sort(b,Collections.reverseOrder());
    
    long res = 0;
    for(int i = 0; i < n; i++)
      res += 1L * a[i] * b[i];
    
    System.out.println(res);
    con.close();
  }
}   

Python realization

Read the input data.

n = int(input())
l1 = list(map(int,input().split()))
l2 = list(map(int,input().split()))

Sort the first array in ascending order, and the second array in descending order.

l1.sort()
l2.sort(reverse = True)

Compute the desired minimum sum.

res = 0
for i in range(n):
  res += l1[i] * l2[i]

Print the answer.

print(res)