문제
N대의 자동차가 주차장에 주차를 하려고 하는데, 주차장에는 주차를 할 수 있는 정확히 N개의 칸이 있다.
각 차의 좌우 너비는 a1… an이며, 각 칸의 좌우 너비는 b1 … bn이다.
각 차들은 자신의 너비 이상의 칸에만 주차가 가능하다.
이 때, 차들이 주차를 할 수 있는 방법의 모든 경우의 수를 출력하는 프로그램을 작성하자.
입력
첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 20)
두 번째 줄에는 a1, a2, … , an가 주어지고,
세 번째 줄에는 b1, b2,…,bn가 주어지며,
모든 너비 입력은 1 ~ 109의 범위의 정수이다.
출력
주차 가능한 방법의 경우의 수를 출력하시오.
해당 값은 C++의 "long long"과 같은 64-bit 정수를 사용해야 할 수도 있다.
예제1
입력
4
1 2 3 4
2 4 3 4
출력
8
출처
USACO 2021 January Bronze