题目详情题解（0）讨论（0）提交记录（0）

CF1909C.Heavy Intervals

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Shiki - Pure Ruby

⠀

You have nn intervals [l1,r1],[l2,r2],…,[ln,rn][l_1, r_1], [l_2, r_2], \dots, [l_n, r_n] , such that li<ril_i < r_i for each ii , and all the endpoints of the intervals are distinct.

The ii -th interval has weight cic_i per unit length. Therefore, the weight of the ii -th interval is ci⋅(ri−li)c_i \cdot (r_i - l_i) .

You don't like large weights, so you want to make the sum of weights of the intervals as small as possible. It turns out you can perform all the following three operations:

  • rearrange the elements in the array ll in any order;
  • rearrange the elements in the array rr in any order;
  • rearrange the elements in the array cc in any order.

However, after performing all of the operations, the intervals must still be valid (i.e., for each ii , li<ril_i < r_i must hold).

What's the minimum possible sum of weights of the intervals after performing the operations?

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt ( 1≤t≤1041 \le t \le 10^4 ). The description of the test cases follows.

The first line of each test case contains a single integer nn ( 1≤n≤1051 \le n \le 10^5 ) — the number of intervals.

The second line of each test case contains nn integers l1,l2,…,lnl_1, l_2, \ldots, l_n ( 1≤li≤2⋅1051 \le l_i \le 2 \cdot 10^5 ) — the left endpoints of the initial intervals.

The third line of each test case contains nn integers r1,r2,…,rnr_1, r_2, \ldots, r_n ( li<ri≤2⋅105l_i < r_i \le 2 \cdot 10^5 ) — the right endpoints of the initial intervals.

It is guaranteed that {l1,l2,…,ln,r1,r2,…,rn}\{l_1, l_2, \dots, l_n, r_1, r_2, \dots, r_n\} are all distinct.

The fourth line of each test case contains nn integers c1,c2,…,cnc_1, c_2, \ldots, c_n ( 1≤ci≤1071 \le c_i \le 10^7 ) — the initial weights of the intervals per unit length.

It is guaranteed that the sum of nn over all test cases does not exceed 10510^5 .

输出格式

For each test case, output a single integer: the minimum possible sum of weights of the intervals after your operations.

输入输出样例

  • 输入#1

    2
2
8 3
12 23
100 100
4
20 1 2 5
30 4 3 10
2 3 2 3

    输出#1

    2400
42

说明/提示

In the first test case, you can make

  • l=[8,3]l = [8, 3] ;
  • r=[23,12]r = [23, 12] ;
  • c=[100,100]c = [100, 100] .

In that case, there are two intervals:

  • interval [8,23][8, 23] with weight 100100 per unit length, and 100⋅(23−8)=1500100 \cdot (23-8) = 1500 in total;
  • interval [3,12][3, 12] with weight 100100 per unit length, and 100⋅(12−3)=900100 \cdot (12-3) = 900 in total.

The sum of the weights is 24002400 . It can be shown that there is no configuration of final intervals whose sum of weights is less than 24002400 .

In the second test case, you can make

  • l=[1,2,5,20]l = [1, 2, 5, 20] ;
  • r=[3,4,10,30]r = [3, 4, 10, 30] ;
  • c=[3,3,2,2]c = [3, 3, 2, 2] .

In that case, there are four intervals:

  • interval [1,3][1, 3] with weight 33 per unit length, and 3⋅(3−1)=63 \cdot (3-1) = 6 in total;
  • interval [2,4][2, 4] with weight 33 per unit length, and 3⋅(4−2)=63 \cdot (4-2) = 6 in total;
  • interval [5,10][5, 10] with weight 22 per unit length, and 2⋅(10−5)=102 \cdot (10-5) = 10 in total;
  • interval [20,30][20, 30] with weight 22 per unit length, and 2⋅(30−20)=202 \cdot (30-20) = 20 in total.

The sum of the weights is 4242 . It can be shown that there is no configuration of final intervals whose sum of weights is less than 4242 .

首页