codeforces-scrape

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

960B.md (2645B)


      1 Source: https://codeforces.com/problemset/problem/960/B
      2 
      3 B. Minimize the error
      4 
      5 time limit per test
      6 
      7 1 second
      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*, each of size *n*. The error, *E*, between these two arrays is defined ![](https://espresso.codeforces.com/84b1d7b07d4ce3641662f45375c8a50d62ec64b3.png). You have to perform exactly *k*1 operations on array *A* and exactly *k*2 operations on array *B*. In one operation, you have to choose one element of the array and increase or decrease it by 1.
     22 
     23 Output the minimum possible value of error after *k*1 operations on array *A* and *k*2 operations on array *B* have been performed.
     24 
     25 Input
     26 
     27 The first line contains three space-separated integers *n* (1 ≤ *n* ≤ 103), *k*1 and *k*2 (0 ≤ *k*1 + *k*2 ≤ 103, *k*1 and *k*2 are non-negative) — size of arrays and number of operations to perform on *A* and *B* respectively.
     28 
     29 Second line contains *n* space separated integers *a*1, *a*2, ..., *a**n* ( - 106 ≤ *a**i* ≤ 106) — array *A*.
     30 
     31 Third line contains *n* space separated integers *b*1, *b*2, ..., *b**n* ( - 106 ≤ *b**i* ≤ 106)— array *B*.
     32 
     33 Output
     34 
     35 Output a single integer — the minimum possible value of ![](https://espresso.codeforces.com/7ab228779016e823448312cefb98ed9221a67116.png) after doing exactly *k*1 operations on array *A* and exactly *k*2 operations on array *B*.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 2 0 0  
     43 1 2  
     44 2 3
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 2
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 2 1 0  
     57 1 2  
     58 2 2
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 2 5 7  
     71 3 4  
     72 14 4
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 1
     79 ```
     80 
     81 Note
     82 
     83 In the first sample case, we cannot perform any operations on *A* or *B*. Therefore the minimum possible error *E* = (1 - 2)2 + (2 - 3)2 = 2.
     84 
     85 In the second sample case, we are required to perform exactly one operation on *A*. In order to minimize error, we increment the first element of *A* by 1. Now, *A* = [2, 2]. The error is now *E* = (2 - 2)2 + (2 - 2)2 = 0. This is the minimum possible error obtainable.
     86 
     87 In the third sample case, we can increase the first element of *A* to 8, using the all of the 5 moves available to us. Also, the first element of *B* can be reduced to 8 using the 6 of the 7 available moves. Now *A* = [8, 4] and *B* = [8, 4]. The error is now *E* = (8 - 8)2 + (4 - 4)2 = 0, but we are still left with 1 move for array *B*. Increasing the second element of *B* to 5 using the left move, we get *B* = [8, 5] and *E* = (8 - 8)2 + (4 - 5)2 = 1.