codeforces-scrape

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

1914D.md (3001B)


      1 Source: https://codeforces.com/problemset/problem/1914/D
      2 
      3 D. Three Activities
      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 Winter holidays are coming up. They are going to last for $n$ days.
     22 
     23 During the holidays, Monocarp wants to try all of these activities exactly once with his friends:
     24 
     25 * go skiing;
     26 * watch a movie in a cinema;
     27 * play board games.
     28 
     29 Monocarp knows that, on the $i$-th day, exactly $a_i$ friends will join him for skiing, $b_i$ friends will join him for a movie and $c_i$ friends will join him for board games.
     30 
     31 Monocarp also knows that he can't try more than one activity in a single day.
     32 
     33 Thus, he asks you to help him choose three distinct days $x, y, z$ in such a way that the total number of friends to join him for the activities ($a_x + b_y + c_z$) is maximized.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     38 
     39 The first line of each testcase contains a single integer $n$ ($3 \le n \le 10^5$) — the duration of the winter holidays in days.
     40 
     41 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^8$) — the number of friends that will join Monocarp for skiing on the $i$-th day.
     42 
     43 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^8$) — the number of friends that will join Monocarp for a movie on the $i$-th day.
     44 
     45 The fourth line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^8$) — the number of friends that will join Monocarp for board games on the $i$-th day.
     46 
     47 The sum of $n$ over all testcases doesn't exceed $10^5$.
     48 
     49 Output
     50 
     51 For each testcase, print a single integer — the maximum total number of friends that can join Monocarp for the activities on three distinct days.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 4
     59 
     60 3
     61 
     62 1 10 1
     63 
     64 10 1 1
     65 
     66 1 1 10
     67 
     68 4
     69 
     70 30 20 10 1
     71 
     72 30 5 15 20
     73 
     74 30 25 10 10
     75 
     76 10
     77 
     78 5 19 12 3 18 18 6 17 10 13
     79 
     80 15 17 19 11 16 3 11 17 17 17
     81 
     82 1 17 18 10 15 8 17 3 13 12
     83 
     84 10
     85 
     86 17 5 4 18 12 4 11 2 16 16
     87 
     88 8 4 14 19 3 12 6 7 5 16
     89 
     90 3 4 8 11 10 8 10 2 20 3
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 30
     97 75
     98 55
     99 56
    100 ```
    101 
    102 Note
    103 
    104 In the first testcase, Monocarp can choose day $2$ for skiing, day $1$ for a movie and day $3$ for board games. This way, $a_2 = 10$ friends will join him for skiing, $b_1 = 10$ friends will join him for a movie and $c_3 = 10$ friends will join him for board games. The total number of friends is $30$.
    105 
    106 In the second testcase, Monocarp can choose day $1$ for skiing, day $4$ for a movie and day $2$ for board games. $30 + 20 + 25 = 75$ friends in total. Note that Monocarp can't choose day $1$ for all activities, because he can't try more than one activity in a single day.
    107 
    108 In the third testcase, Monocarp can choose day $2$ for skiing, day $3$ for a movie and day $7$ for board games. $19 + 19 + 17 = 55$ friends in total.
    109 
    110 In the fourth testcase, Monocarp can choose day $1$ for skiing, day $4$ for a movie and day $9$ for board games. $17 + 19 + 20 = 56$ friends in total.