C. Vasya And The Mushrooms

2*n 타일로 된 버섯농장을 운영중이다.

첫번째 순서대로 a1, a2, a3,,, An

두번째 순서대로 b1, b2, b3,,, Bn

개의 버섯 슬롯이 있고 매 슬롯마다 버섯이 자라며 시간당 가치가 1씩 올라간다. 타일을 움직일 때마다 시간이 1씩 지나고

수확에는 시간이 걸리지 않고 모든 타일을 정확히 한번만 들렀을 때 수확한 버섯 가치의 총합을 최대화하는 문제다.

2*n의 특성을 생각하면 여러가지 경우를 생각 할 수 있다.

     ith

... o o x x

... x x x x

(o는 수확한곳)

이런 상황이라면 o에서 아래로 내려간 후 [1][i-1] 위치의 버섯을 수확해버리면

다시는 그 뒤의 버섯을 수확 할 수 없어서 조건을 만족시키지 못한다.

결국 나올 수 있는 패턴이

이거밖에 없다. 지그재그 부분의 길이만 달라질뿐 패턴은 저기서 달라지지 않는다.

그럼 일단 저걸 n=6일 때 모든 패턴을 그려보자.

(마지막부분 [0][5]는 11인데 1이라 잘못적혀있다)

저기서 1,3이랑 2,4를 보면 패턴이 있다.

1,3만 보면

1의 주황색과 3의 초록색 박스는 동일한 패턴인데 이 중 초록색 박스 부분은

초록색 박스의 순수값의 합*2 만큼의 차이가 있다.

마찬가지의 패턴이 2,4에서도 보인다.

따라서 1,3,5,,, 순으로 보이는 패턴과 2,4,6,,, 순으로 보이는 패턴을 따로 생각하고

각각의 패턴중 첫번째 모양만 누적합을 구한다. 마찬가지로 초록색 박스부분을 빼기 위해 

누적합을 또 구한다.

그 다음 지그재그 모양을 진행하면서 나머지 부분을 잘 합쳐서 최대값을 계산하면 된다.

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
 
typedef long long ll;
 
int n;
ll a[300001];
ll b[300001];
ll ps[300001][2];
ll pss[300001];
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    for (int i = 1; i <= n; ++i)
        scanf("%d", b + i);
 
    ps[1][0] = 0 * a[1] + (2 * n - 1)*b[1];
    for (int i = 2; i <= n; ++i)
        ps[i][0] = ps[i - 1][0] + (i - 1) * a[i] + (2 * n - i)*b[i];
 
    ps[2][1] = (2 * n - 1)*a[2] + 2 * b[2];
    for (int i = 3; i <= n; ++i)
        ps[i][1] = ps[i - 1][1] + (2 * n - i + 1)*a[i] + i * b[i];
 
    for (int i = 1; i <= n; ++i) 
        pss[i] = pss[i - 1] + a[i] + b[i];
 
    ll sum = 0, ans = 0;
 
    for (int i = 1; i <= n + 1; ++i) {
        if (i % 2) {
            sum += (i - 2) * 2 * b[i - 1] + ((i - 2) * 2 + 1)*a[i - 1];
            // ps[][0]
            ans = max(ans, sum + ps[n][0] - ps[i - 1][0] + (pss[n] - pss[i - 1])*(i - 1));
        }
        else {
            sum += (i - 2) * 2 * a[i - 1] + ((i - 2) * 2 + 1)*b[i - 1];
            // ps[][1]
            ans = max(ans, sum + ps[n][1] - ps[i - 1][1] + (pss[n] - pss[i - 1])*(i - 2));
        }
    }
    printf("%lld", ans);
    return 0;
}