https://codeforces.com/contest/1519/problem/D
시간 2초, 메모리 256MB

input :

• n (1 ≤ n ≤ 5000)
• a1, a2, …, an (1 ≤ ai ≤ 107)
• b1, b2, …, bn (1 ≤ bi ≤ 107)

output :

• Print single integer — maximum possible sum after reversing at most one subarray (continuous subsegment) of a.
  부분 배열 하나를 뒤집었을 때 또는 안 뒤집었을 때 가장 큰 합을 가지는 경우의 값을 출력하시오.

조건 :

• You can reverse at most one subarray (continuous subsegment) of the array a.
  Your task is to reverse such a subarray that the sum ai ⋅ bi (1 ~ i) is maximized.
  최대1개의 부분 배열을 뒤집을 수 있습니다. 그 때에 ai ⋅ bi (1 ~ i)까지의 합의 최댓값을 출력하시오.

---

당연히 제일 앞에서 부터 돈다면 시간 초과가 발생한다.

좌우

i에서 시작할 때 좌우로 퍼져 나가도록 한다면? 어떨까
그러면 맨 처음에 모든 배열의 값을 저장해놓은 다음 이 값에서 원래 값을 빼고 뒤집은 값을 더해 주는 거다. 그리고 더이상 뒤집을 수가 없으면 멈춤.

본인포함 우

위의 경우에는 i - 1, i + 1이엿다면
여기선 i, i + 1로 해서 다른 경우를 찾아준다.
그 외의 경우는 동일하다.

이렇게 하고 정답을 출력하도록 하자.

import sys


def check(left, right):
    global ans
    temp = pre

    while left >= 0 and right < n:
        temp -= (a[left] - a[right]) * (b[left] - b[right])
        ans = max(ans, temp)
        left -= 1
        right += 1

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

ans = pre = sum(a[i] * b[i] for i in range(n))

for i in range(n - 1):
    check(i, i + 1)
    check(i - 1, i + 1)
print(ans)