Problem about minimizing sum over all the subarrays

cf_1165_E.md

codeforces

Quite interesing problem. We need to minize function of sum_l sum_r f(l,r), where f(l,r) = sum_i ai * bi, i<-[l,r]. So first of all forget about the fact we have two vectors, try to rewrite sum of all the sum of subarrys in one sum. Should have a form sum_i ai * coef(i, n).

How many subarrays are in the array of length n? The same is how many ordered pairs <i,j>? For each i there (n - i) subarrays starting at this i. The total number is S(n) = sum_i (n - i) = n^2 - n(n-1)/2 = n(n+1)/2.

How many subarrays contain a particular element ai? Well, the number of subarrays in the whole array minus those subarrays which do not cover i, e.g. subbarrays layin in the segment [1, i-1] and [i+1, n]. It means that the answer is coef(i, n) = S(n) - S(i-1) - S(n - i) = n(n - i + 1).

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr lint M = 998244353 ;

int main(int, char**) {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<lint> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    
    vector<lint> b(n);
    for (int i = 0; i < n; ++i)
        cin >> b[i];
    
    // sum sum sum = sum K(i,n) * ai * bi
    // K(i,n) = i * (n - i + 1)
    for (int i = 1; i <= n; ++i) {
        a[i-1] =  a[i-1] * i * (n - i + 1);
    }
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    lint res = 0;
    for (int i = 0; i < n; ++i) {
        res = (res + (a[i]%M * b[n - i - 1]%M)%M)%M;    
    }
    
    cout << res << endl;
    
    return 0;
}