20558번 - 쿼리와 수열 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 61 | 23 | 19 | 35.849% |
문제
이 대회에 쿼리 문제가 굉장히 많다는 것을 여러분들도 눈치챘을 것이다. 쿼리를 사랑하는 출제진들은 수열에 재미없는 쿼리를 하는 문제를 하나 더 내고 싶었지만, 여러분의 반발이 심할 것 같아 대신 쿼리들이 주어졌을때 수열을 구하는 문제를 만들기로 했다.
길이 $N$의 수열 $A$에 구간 최댓값 쿼리를 할 것인데, $[i,j]$에는 $Q_{i,j}$번 쿼리를 할 것이다.
아직 수열 $A$의 값은 정해지지 않았다. $1$부터 $N$까지의 각 $i$에 대해, $A_i$의 값으로 서로 다른 $K_i$개의 값 중 하나를 선택할 수 있는데, $j$번째 값은 $V_{i,j}$이며 그 값을 고르는 비용은 $C_{i,j}$이다.
우리의 목표는 적절히 수열 $A$를 골라 구간 쿼리들의 결과들의 합에서 값들을 고르는 비용을 뺀 값을 최대화하는 것이다.
입력
첫 줄에 $N$이 주어진다. $(1 \leq N \leq 300)$
이후 $N$개의 줄에 걸쳐, $Q_{i,j}$가 주어진다. $i$번째 줄에는 $Q_{i,i}$부터 $Q_{i,N}$까지의 수가 공백으로 구분되어 주어진다. $(0 \leq Q_{i,j} \leq 999)$
이후 $N$개의 인덱스에 대해 값의 후보들의 정보가 다음과 같은 형식으로 주어진다.
- 첫 줄에 $K_i$가 주어진다. $(1 \leq K_i)$
- 이후 $K_i$개의 줄에 걸쳐 $V_{i,j}$와 $C_{i,j}$가 공백으로 구분되어 주어진다. $(0 \leq V_{i,j} \leq 10^8, 0 \leq C_{i,j} \leq 10^{13})$
$K_i$의 합은 $300\,000$ 이하이다.
출력
구간 쿼리들의 결과들의 합에서 값들을 고르는 비용을 뺀 값의 최댓값을 출력한다.
예제 입력 1
5 1 0 2 2 0 0 2 2 0 2 2 2 1 2 0 2 0 27 1 19 2 7 25 1 1 2 8 7 4 18 2 8 7 4 4 2 0 25 4 26
예제 출력 1
78
예제 입력 2
2 1 1 1 2 1 100 2 50 1 1 100
예제 출력 2
-145
출처
High School > 경기과학고등학교 > 나는코더다 2020 송년대회 G번
Camp > Petrozavodsk Programming Camp > Winter 2021 > Day 9: Grand Prix of Suwon G번
Contest > Open Cup > 2020/2021 Season > Stage 13: Grand Prix of Suwon G번
- 문제를 검수한 사람: dlalswp25, koosaga, sebinkim
- 문제를 만든 사람: moonrabbit2
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호