시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 3166 10 8 100.000%

문제

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

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

입력

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

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

출력

첫째 줄에 답을 출력한다.

제한

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

서브태스크 1 (100점)

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

서브태스크 2 (2147483600점)

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

서브태스크 3 (298855점)

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

서브태스크 4 (123456789점)

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

서브태스크 5 (2147483636점)

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

서브태스크 6 (20000255점)

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

서브태스크 7 (1234512033점)

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

  • a1, a2, a3, a4, a5는 -999,999,999 이상 999,999,999 이하의 수 중에서 임의로 결정된다.
  • k ≥ 6일 때, Ska1, a2, ... , ak-1 중 5개를 첨자(index)의 중복 없이 뽑아서 곱한 값들을 모두 더한 값이다. 예를 들어, S7 = a1a2a3a4a5 + a1a2a3a4a6 + a1a2a3a5a6 + a1a2a4a5a6 + a1a3a4a5a6 + a2a3a4a5a6이다. -999,999,999 이상 999,999,999 이하의 수 중에서 1,999,999,999로 나눈 나머지가 Sk와 같은 수를 ak로 정한다.

서브태스크 8 (1578774571점)

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

서브태스크 9 (200073점)

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

서브태스크 10 (1357924680점)

  • (a+ a2x + a3x2 + ... + anxn-1)2 = (b0 + b1x + b2x2 + b3x3 + ... + b2n-2x2n-2)라 할 때, bi들 중 홀수가 짝수보다 많다.

서브태스크 11 (1578574497점)

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

예제 입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

33

노트

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

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

출처

Contest > 구데기컵 > 진짜 최종 구데기컵 2 ➗번

  • 문제를 만든 사람: cozyyg

채점

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.