순환 이동 내적
시간 제한1초메모리 제한512 MB
길이가 N인 두 수열을 각각 임의로 회전시켜 내적의 최댓값을 구해 출력합니다.
문제
길이가 N인 두 수열 X와 Y가 있다. 한 번의 순환 이동은 수열의 마지막 원소를 제거한 뒤 그 원소를 맨 앞에 다시 넣는 작업이다. 예를 들어 {1, 2, 3}을 한 번 순환 이동하면 {3, 1, 2}가 되고, 한 번 더 이동하면 {2, 3, 1}이 된다.
X와 Y 각각에 대해 순환 이동을 0번 이상 원하는 만큼 할 수 있다. 모든 이동을 마친 뒤 점수 S를 다음과 같이 계산한다.
S = X[0] * Y[0] + X[1] * Y[1] + ... + X[N-1] * Y[N-1]
가능한 S의 최댓값을 구하라.
입력
첫째 줄에 정수 N이 주어진다.
둘째 줄에는 X에 들어 있는 N개의 수가 주어진다. 셋째 줄에는 Y에 들어 있는 N개의 수가 주어진다.
N은 60,000 이하의 자연수이다. X와 Y에 들어 있는 모든 수는 0 이상 99 이하의 정수이다.
출력
S의 최댓값을 출력한다.