Prof Kamakoti and IPL queues

All submissions for this problem are available.
To buy the tickets for the opening IPL match between CSK and MI, fans are waiting in multiple queues. The police officers present at the scene want to make all the queues into one single queue which would lead to the fans getting agitated. The police know that they can’t save the situation alone so they ask Prof. Kamakoti for help. Prof Kamakoti goes about modelling the situation as follows… Let $n$ be the number of queues. The queues are numbered from 1 to $n$. The $i^{th}$ queue contains $m_i$ fans. The police are allowed to cyclically rotate each queue as they wish (other permutations are not allowed to avoid too much confusion). Depending on the level of frustration, an "agitation value" and "temper value" is assigned to each fan. To form a single queue, the existing queues (after possibly cyclically rotating them). are joined one after the other, in order of their numbering. Note that a queue can be cyclically rotated only before joining it to any other queues. The net agitation level of the final queue is calculated as follows: for queues $q_i$ and $q_{i+1}$, let the agitation value of the last fan in the $i^{th}$ queue be $x_1$, the temper value of the last fan in the $i^{th}$ queue be $y_1$ and the agitation value of the first fan in the $i+1^{th}$ queue be $x_2$. Then, the contribution to the net agitation level of the final queue will be $y_1 \times x_1  x_2$, where $x_1x_2$ denotes the absolute value of $x_1x_2$. Therefore, the net agitation level of the final queue will be the sum of contributions from all pairs of queues $q_i$ and $q_{i+1}$ for $1 \le i < n$. Prof Kamakoti, being a computer scientist, doesn’t believe that the police would rotate the queues optimally and hence decides to calculate the worst case net agitation level. If he gives this as a programming assignment, can you calculate it? ###Input:  The first line of input contains a single integer $n$ denoting the number of queues.  $3n$ lines follow, describing the $n$ queues.  For the description of the $i^{th}$ queue, the first line contains $m_i$, the number of fans in the $i^{th}$ queue.  The second line contains $m_i$ spaceseparated integers $ag_1, ag_2, ..., ag_{m_i}$, with $ag_j$ denoting the agitation value of the $j^{th}$ fan.  The third line contains $m_i$ spaceseparated integers $tm_1, tm_2, ..., tm_{m_i}$, with $tm_j$ denoting the temper value of the $j^{th}$ fan. ###Output: Output a single integer corresponding to the worst case net agitation level of the final queue. Note that the worst case net agitation level is the maximum net agitation level which is possible for any rotation of the smaller queues. ###Constraints  $1 \leq n \leq 3 \times 10^5$  Total number of fans over all the queues in a single test file won't exceed $3 \times 10^5$  $m_i \geq 5$  $0 \leq ag_i, tm_i \leq 10^6+10$ ###Sample Input: 3 3 1 2 3 1 1 1 2 3 2 2 2 2 4 5 3 3 ###Sample Output: 8 ###EXPLANATION: Let the fans be represented by their agitation values. Hence the queues are: Queue 1 : 1, 2, 3 (temper value is 1 for all fans) Queue 2 : 3, 2 (temper value is 2 for all fans) Queue 3 : 4, 5 (temper value is 3 for all fans) All possible cyclic rotations are illustrated below: 01) 1233245 = 33 * 1 + 24 * 2 = 4 02) 3123245 = 23 * 1 + 24 * 2 = 5 03) 2313245 = 13 * 1 + 24 * 2 = 6 04) 1232345 = 32 * 1 + 34 * 2 = 3 05) 3122345 = 22 * 1 + 34 * 2 = 2 06) 2312345 = 12 * 1 + 34 * 2 = 3 07) 1233254 = 33 * 1 + 25 * 2 = 6 08) 3123254 = 23 * 1 + 25 * 2 = 7 09) 2313254 = 13 * 1 + 25 * 2 = 8 10) 1232354 = 32 * 1 + 35 * 2 = 5 11) 3122354 = 22 * 1 + 35 * 2 = 4 12) 2312354 = 12 * 1 + 35 * 2 = 5 Thus, the worstcase net agitation level for the final queue is 8.Author:  teja349 
Tags  teja349 
Date Added:  5042018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions