28433번 - 게리맨더링 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1543 | 385 | 301 | 27.364% |
문제
길이 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어집니다. 이 수열을 원하는 개수의 연속된 구간으로 나누어서, 각 구간의 합을 계산합니다. 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과하도록 할 수 있을까요?
입력
첫 줄에 테스트케이스의 수 $T$가 주어집니다. $(1 \le T \le 10\,000)$
각 테스트케이스의 첫 줄에 배열의 길이 $N$이 주어집니다. $(1 \le N \le 200\,000)$
둘째 줄에 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어집니다. $(-10^9 \le A_i \le 10^9)$
입력에서 주어진 $N$의 합은 $200\,000$을 넘지 않습니다.
출력
각 테스트케이스마다 한 줄에 하나씩, 구간의 합이 양수인 것의 개수가 음수인 것의 개수를 초과하도록 할 수 있다면 “YES”를, 아니면 “NO”를 출력하세요.
예제 입력 1
4 4 2 2 -100 -100 5 -2 3 -2 3 -2 6 -1 1 -1 1 -1 2 7 -3 1 -4 5 -9 2 -6
예제 출력 1
YES YES YES NO
- 첫 번째 테스트케이스에서는 구간을 $[2]; [2]; [-100, -100]$과 같이 나누면 됩니다.
- 두 번째 테스트케이스에서는 구간을 $[-2, 3]; [-2]; [3, -2]$와 같이 나누면 됩니다.
- 세 번째 테스트케이스에서는 구간을 $[-1, 1, -1, 1, -1, 2]$와 같이 나누면 됩니다.
- 네 번째 테스트케이스에서는 어떻게 나누어도 합이 양수인 구간의 개수가 음수인 구간의 개수를 넘도록 할 수 없습니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호