문제
한 배열 A[1..n] 에 대하여 부배열은 1≤i≤j≤n인 A[i..j] 를 말한다.
부배열 A[i..j]의 합은 A[i]+…+A[j] 이다. 원소가 양의 정수인 두 개의 배열 A[1..n]와 B[1..m]가 주어져 있다.
A의 부 배열의 합에 B의 부배열의 합을 더해서 t가 되는 모든 부배열 쌍의 개수를 구하는 프로그램을 작성 하시오.
예를 들어, A=(1, 3, 1, 2), B=(1, 3, 2)이고 t=5 인 경우, 합이 5가 되는 A와 B의 부배열 쌍의 개수는 아래와 같이 7가지이다.
A[1]+B[1]+B[2] = A[1]+A[2]+B[1] = A[2]+B[3] = A[2]+A[3]+B[1] = A[3]+B[1]+B[2] = A[3]+A[4]+B[3] = A[4]+B[2] = 5
입력
첫째 줄에는 t(t≤10,000)가 주어진다.
둘째 줄에는 배열 A의 크기 n(n≤1,000 ) 이 주어지고,
셋째 줄에는 A의 원소들이 A[1]부터 차례대로 주어진다.
넷째 줄에는 배열 B의 크기 m(m≤1,000 ) 이 주어지고,
마지막 줄에는 B의 원소들이 B[1]부터 차례대로 주어진다.
원소의 값은 1,000을 넘지 않는 양의 정수이며 숫자 사이에는 빈칸이 하나 있다.
출력
첫째 줄에 합이 t 가 되는 A 와 B 의 부배열 쌍의 개수를 출 력한다.
합이 t 가 되는 부배열 쌍이 없는 경우에는 숫자 0을 출력한다.
예제1
입력
5
4
1312
3
132
출력
7
태그
출처
KOI 전국 2001 고1