테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 이동 ======

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

===== 코드 =====
<dkpr py>
"""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()

</dkpr>
  * Dependency: [[:ps:teflib:fft#multiply|teflib.fft.multiply]]

{{tag>BOJ ps:problems:boj:플래티넘_2}}