Sum of Subarrays from Two Arrays
Time limit2sMemory limit64 MB
Count pairs of contiguous subarrays, one from each of two arrays, whose sums add up to a given target T.
- Level
Medium5 of 10
- Topics
- Array, Hash map, Prefix sum
- Solved
- No attempts yet
Problem
For an array A[1], A[2], ..., A[n], a contiguous subarray is A[i], A[i+1], ..., A[j] where 1 <= i <= j <= n. Its sum is A[i] + ... + A[j].
Given two integer arrays A[1], ..., A[n] and B[1], ..., B[m], count the number of pairs made of one contiguous subarray from A and one contiguous subarray from B such that their sums add up to T.
sum(A[i..j]) + sum(B[p..q]) = T
Input
The first line contains T (-1,000,000,000 <= T <= 1,000,000,000).
The next line contains n (1 <= n <= 1,000), followed by a line containing n integers A[1], ..., A[n].
The next line contains m (1 <= m <= 1,000), followed by a line containing m integers B[1], ..., B[m].
Every array element is an integer whose absolute value is at most 1,000,000.
Output
Print the answer on the first line. If there is no valid pair, print 0.