codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1165E.md (1476B)


      1 Source: https://codeforces.com/problemset/problem/1165/E
      2 
      3 E. Two Arrays and Sum of Functions
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given two arrays $a$ and $b$, both of length $n$.
     22 
     23 Let's define a function $f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i$.
     24 
     25 Your task is to reorder the elements (choose an arbitrary order of elements) of the array $b$ to minimize the value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$. Since the answer can be very large, you have to print it modulo $998244353$. Note that you should minimize the answer but not its remainder.
     26 
     27 Input
     28 
     29 The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$ and $b$.
     30 
     31 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the $i$-th element of $a$.
     32 
     33 The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_j \le 10^6$), where $b_j$ is the $j$-th element of $b$.
     34 
     35 Output
     36 
     37 Print one integer — the minimum possible value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$ after rearranging elements of $b$, taken modulo $998244353$. Note that you should minimize the answer but not its remainder.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 5
     45 1 8 7 2 4
     46 9 7 2 9 3
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 646
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 1
     59 1000000
     60 1000000
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 757402647
     67 ```
     68 
     69 Input
     70 
     71 ```
     72 2
     73 1 3
     74 4 2
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 20
     81 ```