codeforces-scrape

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

1036D.md (1989B)


      1 Source: https://codeforces.com/problemset/problem/1036/D
      2 
      3 D. Vasya and Arrays
      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 Vasya has two arrays $A$ and $B$ of lengths $n$ and $m$, respectively.
     22 
     23 He can perform the following operation arbitrary number of times (possibly zero): he takes some consecutive subsegment of the array and replaces it with a single element, equal to the sum of all elements on this subsegment. For example, from the array $[1, 10, 100, 1000, 10000]$ Vasya can obtain array $[1, 1110, 10000]$, and from array $[1, 2, 3]$ Vasya can obtain array $[6]$.
     24 
     25 Two arrays $A$ and $B$ are considered equal if and only if they have the same length and for each valid $i$ $A_i = B_i$.
     26 
     27 Vasya wants to perform some of these operations on array $A$, some on array $B$, in such a way that arrays $A$ and $B$ become equal. Moreover, the lengths of the resulting arrays should be maximal possible.
     28 
     29 Help Vasya to determine the maximum length of the arrays that he can achieve or output that it is impossible to make arrays $A$ and $B$ equal.
     30 
     31 Input
     32 
     33 The first line contains a single integer $n~(1 \le n \le 3 \cdot 10^5)$ — the length of the first array.
     34 
     35 The second line contains $n$ integers $a_1, a_2, \cdots, a_n~(1 \le a_i \le 10^9)$ — elements of the array $A$.
     36 
     37 The third line contains a single integer $m~(1 \le m \le 3 \cdot 10^5)$ — the length of the second array.
     38 
     39 The fourth line contains $m$ integers $b_1, b_2, \cdots, b_m~(1 \le b_i \le 10^9)$ - elements of the array $B$.
     40 
     41 Output
     42 
     43 Print a single integer — the maximum length of the resulting arrays after some operations were performed on arrays $A$ and $B$ in such a way that they became equal.
     44 
     45 If there is no way to make array equal, print "-1".
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 5  
     53 11 2 3 5 7  
     54 4  
     55 11 7 3 7
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 3
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 2  
     68 1 2  
     69 1  
     70 100
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 -1
     77 ```
     78 
     79 Input
     80 
     81 ```
     82 3  
     83 1 2 3  
     84 3  
     85 1 2 3
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 3
     92 ```