25438번 - 메기 농장 서브태스크다국어언어 제한함수 구현
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 163 | 38 | 36 | 27.692% |
문제
부 뎅클렉은 메기 양어장을 가지고 있다. 양어장은 $N \times N$ 격자칸 모양이다. 격자의 칸들은 같은 크기의 정사각형이다. 격자의 열들은 서쪽에서 동쪽으로 $0$부터 $N - 1$까지 번호가 붙어 있고, 행들은 남쪽에서 북쪽으로 $0$부터 $N - 1$까지 번호가 붙어있다. 열 $c$, 행 $r$에 ($0 \le c \le N - 1$, $0 \le r \le N - 1$) 있는 칸을 칸 $(c, r)$로 부른다.
양어장에는 $M$ 마리의 메기가 있다. 메기들은 $0$부터 $M - 1$까지 번호가 붙어 있고, 모두 다른 칸에 있다. 각각의 $i$에 대해 ($0 \le i \le M - 1$) 메기 $i$는 칸 $(X[i], Y[i])$에 있고, 그 무게는 $W[i]$그램이다.
부 뎅클렉은 메기를 잡기 위해 낚시터를 지으려고 한다. 열 $c$에 있는 길이 $k$인 낚시터는 ($0 \le c \le N - 1$, $1 \le k \le N$), 열 $c$의 행 $0$부터 행$k - 1$까지를 덮는 직사각형이다. 즉, 낚시터는 칸들 $(c, 0), (c, 1), \ldots, (c, k - 1)$를 덮는다. 각 열에 대해서 부 뎅클렉은 특정한 길이의 낚시터를 짓거나, 낚시터를 전혀 짓지 않는 것 중 선택을 할 수 있다.
메기 $i$를 ($0 \le i \le M - 1$) 잡기 위해서는 메기 $i$의 위치의 서쪽이나 동쪽에 인접한 칸을 낚시터가 덮어야 하며, 메기 $i$의 위치는 낚시터가 덮지 않아야 한다. 다시 말하면,
- 칸들 $(X[i] - 1, Y[i])$와 $(X[i] + 1, Y[i])$ 중 적어도 하나가 낚시터에 덮이고,
- 칸 $(X[i], Y[i])$는 낚시터에 덮이지 않아야 한다.
예를 들어, $N = 5$인 양어장에 $M = 4$마리의 메기가 있다고 하자.
- 메기 $0$의 위치는 칸 $(0, 2)$이고 그 무게는 $5$그램이다.
- 메기 $1$의 위치는 칸 $(1, 1)$이고 그 무게는 $2$그램이다.
- 메기 $2$의 위치는 칸 $(4, 4)$이고 그 무게는 $1$그램이다.
- 메기 $3$의 위치는 칸 $(3, 3)$이고 그 무게는 $3$그램이다.
부 뎅클렉이 낚시터를 지을 수 있는 방법 중 하나는 아래와 같다.
| 낚시터 짓기 전 | 낚시터 지은 후 |
|---|---|
칸에 표시된 자연수는 그 칸에 있는 메기의 무게이다. 색칠된 칸들이 낚시터에 덮인 곳이다. 이 경우 잡을 수 있는 메기는 메기 $0$(칸 $(0, 2)$에 위치)과 메기 $3$(칸 $(3, 3)$에 위치)이다. 메기 $1$(칸 $(1, 1)$에 위치)는 그 칸이 낚시터에 덮여 있어 잡을 수 없다. 메기 $2$(칸 $(4, 4)$에 위치)는 서쪽이나 동쪽에 인접한 칸이 낚시터로 덮인 것이 없어 잡을 수 없다.
부 뎅클렉은 잡을 수 있는 메기의 무게의 합이 가장 크도록 낚시터를 짓고 싶다. 잡을 수 있는 메기의 최대 무게 합을 계산하는 프로그램을 작성하라.
구현
당신은 다음 함수를 구현해야 한다:
int64 max_weights(int N, int M, int[] X, int[] Y, int[] W)
- $N$: 양식장의 크기.
- $M$: 메기의 마리 수.
- $X$, $Y$: 메기의 위치를 표현한 크기 $M$인 배열들.
- $W$: 메기의 무게를 표현한 크기 $M$인 배열.
- 이 함수는 부 뎅클렉이 낚시터를 지어서 잡을 수 있는 최대의 메기 무게 합을 리턴해야 한다.
- 이 함수는 정확히 한번 호출된다.
예제
다음 호출을 생각하자:
max_weights(5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3])
이 예제는 위의 문제 설명에 있는 것과 같다.
문제 설명에 있는 것과 같이 낚시터를 지으면, 부 뎅클렉은 메기 $0$과 $3$을 잡을 수 있고, 무게의 합은 $5 + 3 = 8$ 그램이다. 이 방법이 최선이며 함수는 $8$을 리턴해야 한다.
제한
- $2 \le N \le 100\,000$
- $1 \le M \le 300\,000$
- $0 \le X[i] \le N - 1$, $0 \le Y[i] \le N - 1$ ($0 \le i \le M - 1$)
- $1 \le W[i] \le 10^9$ ($0 \le i \le M - 1$)
- 메기들의 위치는 모두 다르다. 즉, $X[i] \neq X[j]$ 혹은 $Y[i] \neq Y[j]$ ($0 \le i \lt j \le M - 1$).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $X[i]$가 짝수 ($0 \le i \le M - 1$) |
| 2 | 6 | $X[i] \le 1$ ($0 \le i \le M - 1$) |
| 3 | 9 | $Y[i] = 0$ ($0 \le i \le M - 1$) |
| 4 | 14 | $N \le 300$, $Y[i] \le 8$ ($0 \le i \le M - 1$) |
| 5 | 21 | $N \le 300$ |
| 6 | 17 | $N \le 3000$ |
| 7 | 14 | 각 열에는 최대 $2$ 마리의 메기가 있다. |
| 8 | 16 | 추가적인 제한이 없다. |
샘플 그레이더
샘플 그레이더는 다음 형식으로 입력을 읽는다:
- line $1$: $N \, M$
- line $2 + i$ ($0 \le i \le M - 1$): $X[i] \, Y[i] \, W[i]$
샘플 그레이더는 다음 형식으로 답을 출력한다:
- line $1$:
max_weights의 리턴 값
첨부
출처
Olympiad > International Olympiad in Informatics > IOI 2022 > Day 1 1번
- 문제를 만든 사람: Lim Rui Yuan
제출할 수 있는 언어
C++17, C++20, C++17 (Clang), C++20 (Clang)
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호