Official Analysis (C++)

Explanation

Simplification

First off, let's just do away with all that weird subarray stuff and look at the following simplification:

Given two arrays $a$ and $b$, permute $b$ to minimize $\sum_{i=0}^{n-1} a_i \cdot b_i$.

This simpler one is solvable by a greedy approach. We match the largest element in $a$ to the smallest one in $b$, the second-largest in $a$ to the second-smallest in $b$, and so on and so forth until we've matched all of them.

The intuition behind this is that we want to minimize the impact larger elements in $a$ will have on the sum so we match them to smaller ones in $b$.

Actual Problem

Unfortunately, the original problem isn't as simple.

However, notice that we can precompute the number of occurrences a particular index $k$ will appear among all the summations.

With this, if we know $a_2 \cdot b_2$ will appear exactly $5$ times in the summation, then we can preemptively multiply $a_2$ by $5$ before doing the matching in our simplification.

If we use 0-indexing, each index $k$ is included in $(k + 1) \cdot (n - k)$ positions. This is because there's $k+1$ start positions for subarrays on the left and $n-k$ end positions on the right.

Then, we can multiply each element of $a$ by its number of occurrences to reduce this to our simpler problem!

Implementation

Time Complexity: $\mathcal{O}(n \log n)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {
	int len;

Copy
import java.io.*;
import java.util.*;

public class Permutator {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int len = Integer.parseInt(read.readLine());
		int[] a = Arrays.stream(read.readLine().split(" "))
		              .mapToInt(Integer::parseInt)
		              .toArray();

Copy
len_ = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

subarr_num = [(i + 1) * (len_ - i) for i in range(len_)]

actual_a = [i * j for i, j in zip(subarr_num, a)]

actual_a.sort()
b.sort(reverse=True)

total = sum(i * j for i, j in zip(actual_a, b))
print(total)