Two Arrays
Tag(s):

## Algorithms, Binary search algorithm, Medium, Prefix sum, Searching algorithm, Two pointer, prefix-sum

Problem
Editorial
Analytics

Let's define the matching number for two arrays X and Y, each with size n, as the number of pairs of indices $(i,j)$ such that $X_i = Y_j$ ($1 \le i,j \le n$).

You are given an integer K and two arrays A and B with sizes N and M respectively. Find the number of ways to pick two subarrays with equal size, one from array A and the other from array B, such that the matching number for these two subarrays is $\ge K$.

Note: a subarray consists of one or more consecutive elements of an array.

Constraints

• $1 \le N , M \le 2,000$

• $1 \le A_i \le 1,000,000,000$ for each valid i

• $1 \le B_i \le 1,000,000,000$ for each valid i

• $1 \le K \le NM$

Input format

The first line of the input contains three space-separated integers N, M and K.

The second line contains N space-separated integers $A_1, \dots, A_N$.

The third line contains M space-separated integers $B_1, \dots, B_M$.

Output Format

Print a single line containing one number denoting the number of ways to choose the pair of subarrays.

SAMPLE INPUT
3 3 1
1 2 3
1 2 3

SAMPLE OUTPUT
8

Explanation

The following pairs of subarrays have matching number $\ge 1$: (, ), (, ), (, ), ([1, 2], [1, 2]), ([1, 2], [2, 3]), ([2, 3], [1, 2]), ([2, 3], [2, 3]), ([1, 2, 3], [1, 2, 3]).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

December Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Data Structures > Arrays
• Algorithms > Dynamic Programming
• Math > Combinatorics