두 배열의 부분 배열 합
시간 제한2초메모리 제한64 MB
두 배열에서 각각 연속 부분배열을 하나씩 골라 합이 T가 되는 쌍의 개수를 구하는 문제입니다.
문제
배열 A[1], A[2], ..., A[n]에서 부 배열은 1 <= i <= j <= n을 만족하는 연속한 원소 A[i], A[i+1], ..., A[j]를 말한다. 이 부 배열의 합은 A[i] + ... + A[j]이다.
정수 배열 A[1], ..., A[n]과 B[1], ..., B[m]이 주어진다. A에서 고른 부 배열 하나와 B에서 고른 부 배열 하나의 합을 더했을 때 T가 되는 쌍의 개수를 구하라.
sum(A[i..j]) + sum(B[p..q]) = T
입력
첫째 줄에 T (-1,000,000,000 <= T <= 1,000,000,000)가 주어진다.
다음 줄에 n (1 <= n <= 1,000)이 주어지고, 그 다음 줄에 정수 n개 A[1], ..., A[n]이 주어진다.
다음 줄에 m (1 <= m <= 1,000)이 주어지고, 그 다음 줄에 정수 m개 B[1], ..., B[m]이 주어진다.
각 배열의 원소는 절댓값이 1,000,000 이하인 정수이다.
출력
첫째 줄에 답을 출력한다. 조건을 만족하는 쌍이 하나도 없으면 0을 출력한다.