이동

• 고속 푸리에 변환 (Fast Fourier Transform, FFT)을 써서 합성곱을 구하는 전형적인 문제.
• 수열 한개를 두번 이어 붙인 후, FFT로 다항식 곱셈을 해서 얻어지는 수열의, N-1부터의 N개 항이 우리가 원하는 합성곱이다.
  • 수열을 바꾸지 않고 그냥 다항식 곱셈을 해서 수열을 얻고, i번째 항과 N+i번째 항을 더하는 방식으로 합성곱 수열을 계산할 수도 있다.
• 시간복잡도는 고속 푸리에 변환에 필요한 O(nlogn)

"""Solution code for "BOJ 1067. 이동".

- Problem link: https://www.acmicpc.net/problem/1067
- Solution link: http://www.teferi.net/ps/problems/boj/1067
"""

from teflib import fft

MAX = 100


def main():
    N = int(input())
    X = [int(x) for x in input().split()]
    Y = [int(x) for x in input().split()]

    res = fft.multiply(X + X, Y[::-1])
    print(max(res[N - 1:N + N - 1]))


if __name__ == '__main__':
    main()

• Dependency: teflib.fft.multiply