18827번 - 연속합 2147483647 서브태스크

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, −4, 3, 1, 5, 6, −35, 12, 21, −1이라는 수열이 주어졌다고 하자. 여기서 정답은 12 + 21인 33이 정답이 된다.

첫째 줄에 자연수 n이 주어진다.

둘째 줄에는 수열을 구성하는 n개의 정수 a_i들이 공백을 사이에 두고 주어진다.

첫째 줄에 답을 출력한다.

• 1 ≤ n ≤ 300,000
• -1,000,000,000 ≤ a_i ≤ 1,000,000,000 (단, 서브태스크 11은 예외)

• 수열의 모든 수가 양수이다. 즉, 모든 1 ≤ i ≤ n에 대해 a_i > 0이다.

• 수열의 모든 수가 음수이다. 즉, 모든 1 ≤ i ≤ n에 대해 a_i < 0이다.

• 양의 정수 x에 대해 f(x) = (x의 각 자리 숫자의 세제곱의 합)이라 하고, f¹(x) = f(x), f^k(x) = f(f^k-1(x)) (k > 1)라 하자. f^k(n) = 1인 양의 정수 k가 존재한다.

• 입력으로 주어진 수열의 가장 긴 증가하는 부분 수열의 길이가 318의 배수이다. (부분 수열은 연속하지 않아도 된다.)

• 이 서브태스크의 데이터는 예제 하나뿐이다. 아니, 예제도 안 돌려보고 코드를 제출하는 사람이 있나요?

• 이 서브태스크의 데이터도 역시 하나인데, 출제자가 직접 손으로 타이핑하여 만들었다.
• 이 서브태스크의 데이터는 다른 서브태스크의 데이터에 들어 있지 않다.

이 서브태스크에서 n ≥ 6이며, 이 서브태스크의 모든 데이터는 다음과 같은 과정을 통해 생성되었다.

• a₁, a₂, a₃, a₄, a₅는 -999,999,999 이상 999,999,999 이하의 수 중에서 임의로 결정된다.
• k ≥ 6일 때, S_k는 a₁, a₂, ... , a_k-1 중 5개를 첨자(index)의 중복 없이 뽑아서 곱한 값들을 모두 더한 값이다. 예를 들어, S₇ = a₁a₂a₃a₄a₅ + a₁a₂a₃a₄a₆ + a₁a₂a₃a₅a₆ + a₁a₂a₄a₅a₆ + a₁a₃a₄a₅a₆ + a₂a₃a₄a₅a₆이다. -999,999,999 이상 999,999,999 이하의 수 중에서 1,999,999,999로 나눈 나머지가 S_k와 같은 수를 a_k로 정한다.

• 입력으로 주어진 수열의 가장 긴 감소하지 않는 부분 수열의 길이를 p, 가장 긴 증가하지 않는 부분 수열의 길이를 q라고 할 때, pq ≥ n이다. (부분 수열은 연속하지 않아도 된다.)

• 이 서브태스크에는 데이터가 없다.

• (a₁ + a₂x + a₃x² + ... + a_nx^n-1)² = (b₀ + b₁x + b₂x² + b₃x³ + ... + b_2n-2x^2n-2)라 할 때, b_i들 중 홀수가 짝수보다 많다.

• 이 서브태스크에 한하여 "제한" 부분에 있는 a_i 제한이 적용되지 않는다. 즉, a_i의 절댓값은 1,000,000,000보다 클 수 있다. a_i는 여전히 정수이며, 정규 표현식으로 (-?[1-9][0-9]*|0)의 형태로 주어진다.
• 입력으로 들어오는 두 번째 줄의 길이(문자의 개수)는 3,600,000 이상 10,000,000 이하이다.

이 문제를 풀었을 때의 점수는 다음과 같이 계산한다.

• (맞은 서브태스크의 배점의 총합 + X) mod 2147483648
• X = 328 (기본 점수)