25574번 - ABC 배열 놀이 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 60 | 23 | 21 | 43.750% |
문제
세 어린이 Alice, Bob, Chris는 정수 배열을 이용한 놀이를 즐겨한다.
먼저 길이가 n인 정수배열 V를 고른다 (V[i]는 i번째 원소이며 i = 1, 2, ..., n이다). 1 ≤ i ≤ j ≤ n인 인덱스 i, j에 대해 V[i, j]는 V의 i번째부터 j번째 원소까지를 포함한 길이 (j-i+1)인 부분배열로 정의한다.
다음으로 세 개의 정수 a, b, c를 고르는데 이는 앞으로 세 어린이가 고를 부분배열의 길이를 나타낸다. Alice는 길이가 a인 V의 부분 배열을 고르고 (해당 부분 배열을 A라 하자), Bob은 길이가 b인 부분 배열을 고르고 (이를 B라 하자), Chris는 길이가 c인 부분 배열을 고른다 (이를 C라 하자). 단, 이 세 부분 배열은 공통된 원소를 포함해서는 안된다 (즉, 세 부분 배열이 겹치도록 고를 수 없다).
예를 들어 V = [2, 0, -2, -2] 이고 a = 2, b = 1, c = 1 이라면 A = V[1, 2], B = V[3, 3], C = V[4, 4]가 되도록 고르는 것은 괜찮지만, A = V[1, 2], B = V[2, 2], C = V[1, 1] 로 고를 수는 없다 (후자의 경우 A와 B가 두 번째 원소인 V[2]를 공통으로 포함하고, A와 C는 첫 번째 원소인 V[1]를 공통으로 포함한다).
세 어린이는 각자 자신이 고른 부분 배열의 원소를 모두 더한 후, 이렇게 얻어진 세 개의 정수를 (각 부분 배열의 원소 총합을 SA, SB, SC라 하자) 모두 곱하여 최종 점수를 구한다 -- 즉 SA × SB × SC가 최종 점수가 된다.
앞선 예제에서 A = V[1, 2], B = V[3, 3], C = V[4, 4] 를 골랐다면 SA = 2+0 = 2, SB = -2, SC = -2가 되고, SA × SB × SC = 8이 된다. 만약 A = V[1, 2], B = V[4, 4], C = V[3, 3]을 고르더라도 결과는 같다. 하지만 A = V[3, 4], B = V[1, 1], C = V[2, 2]를 고른다면 SA = -4, SB = 2, SC = 0이 되어 최종 점수는 0이 된다. 이 예제에서 세 어린이가 달성할 수 있는 최종 점수의 최댓값은 8이다.
입력으로 V, n, a, b, c가 주어졌을 때, 세 어린이가 협동하여 얻을 수 있는 최종 점수의 최댓값을 구해보자.
입력
입력 첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 걸쳐 주어지며 첫 줄에 n, a, b, c가 공백으로 구분되어 주어진다. 둘째 줄에는 배열 V의 원소인 n개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 10
- 3 ≤ n ≤ 100,000
- 1 ≤ a, b, c ≤ n-2
- a + b + c ≤ n
- -106 ≤ V[i] ≤ 106 (i = 1, 2, ..., n)
- V의 부분 배열 중 길이가 a 혹은 b 혹은 c인 모든 부분 배열에 대하여 해당 부분 배열의 원소 총합의 절댓값은 106을 초과하지 않는다. 따라서 모든 테스트 케이스의 정답은 -1018 이상 1018 이하임이 보장된다.
예제 입력 1
5 4 2 1 1 2 0 -2 -2 6 1 1 1 2 -2 -3 3 1 -1 7 2 2 2 0 1 -2 3 -4 5 -6 8 2 2 2 1 -1 1 -1 1 -1 1 -1 3 1 1 1 -1000000 -1000000 -1000000
예제 출력 1
8 18 1 0 -1000000000000000000
예제 1: 본문에서 다루었다.
예제 2: A = V[2, 2], B = V[3, 3], C = V[4, 4]를 고르는 것이 한 가지 방법이다.
예제 3: A = [1, 2], B = [3, 4], C = [5, 6]을 고르면 된다.
예제 4: 모든 길이 2인 부분 배열의 원소합은 0이다.
예제 5: 추가 설명 없음.
시간 제한
- Java 8: 3 초
- Python 3: 2 초
- PyPy3: 2 초
- Java 8 (OpenJDK): 3 초
- Java 11: 3 초
- Kotlin (JVM): 3 초
- Java 15: 3 초
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호