1804번 - 랩싸기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 198 | 53 | 42 | 29.577% |
문제
조교들은 회식을 끝내고 많은 음식들이 남게 됐다. 그래서 조교는 이 남은 음식물을 랩에 싸서 보관하기로 결정했다.
N개의 음식물들이 2*B 격자에 흩어져서 배치되어 있다. 그리고 랩은 오직 직사각형 모양으로만 쌀 수 있다.
우리에겐 K개의 랩이 있다. 랩은 마음대로 늘릴 수 있기 때문에 한 랩의 가로, 세로 너비 제한은 없다.
| 김치 | 회 | 회 | 족발 | 족발 | ||||
| 라면 | 라면 | 라면 |
위와 같이 음식이 남았을 때는 김치와 라면을 2*3 모양으로 싸고, 회와 족발을 1*4 모양으로 싸면 총 랩을 싸야하는 면적이 10이 된다.
문제는 이렇게 음식들의 위치가 주어졌을 때 모든 음식을 싸기 위해 필요한 랩의 최소 면적을 구하는 것이다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), K(1 ≤ K ≤ N), B(1 ≤ B ≤ 15,000,000)가 공백으로 구분되어 입력된다. 다음 N개의 줄에 음식이 있는 위치가 주어진다.
출력
모든 음식을 싸기 위해 필요한 랩의 최소 면적을 출력한다.
예제 입력 1
8 2 9 1 2 1 6 1 7 1 8 1 9 2 2 2 3 2 4
예제 출력 1
10
출처
Olympiad > USA Computing Olympiad > 2004-2005 Season > USACO US Open 2005 Contest > Gold 1번
- 문제를 번역한 사람: author6
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호