Informatica Online Judge

  오펜스 게임2 [1002 / 03EA]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 16   Total Tried : 186


The Champion of this Problem (C++) : gs17044 - ms / 1188byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

오펜스 게임 $1$에서 경곽이는 아무런 아이템, 방어구 없이 도전하여 상당히 고전했다.

이번에는 $M$개의 방어구와 $K$개의 엘릭서를 가지고 다시 도전한다.

경곽이는 $M$개의 방어구 중 최소 $0$개에서 최대 $M$개를 장착한 상태로 게임에 도전할 수 있다.

이번 게임에서 방어구의 역할은 체력을 늘려주는 역할을 한다. 만약 장착한 방어구들의 방어력의 합이 $d$이고 체력이 $h$라면 기본적으로 $h+d$의 체력으로 게임을 시작하는 것과 같다.

이번에는 출발점$(0,0)$에서 출발하여 도착점$(1000, 1000)$에 $HP$를 $0$이상으로 하여 도착하는 것이 목표이다. 도중에 $HP$가 $0$ 미만이 되면 전투불능이 되어 게임에서 실패한다.

그리고 출발점과 도착점 사이에는 $N$개의 안전영역이 있다.

출발점, 도착점, 각 안전영역을 이동할 때는 이동거리에 비례하는 만큼의 데미지를 받게 된다.

이 때 이동거리는 Manhattan distance(또는 택시거리)로 계산한다.

만약 출발점$(0,0)$에서 안전영역$(10, 10)$으로 이동한다면 이 때 이동거리는 $20$이므로 데미지를 $20$만큼 받게 된다.

만약 체력과 방어력의 합이 $20$미만이라면 이동할 수 없다.

안전영역에서는 엘릭서를 먹을 수 있다. 엘릭서를 먹으면 체력+방어력 만큼의 체력을 모두 회복한다. 단 엘릭서는 $K$개 뿐이다.

이 문제의 목적은 안전영역의 수 $N$과 각 영역의 좌표 및 엘릭서의 수 $K$가 주어지고, $M$개의 방어구의 방어력들과 기본 체력 $h$가 주어질 때, 최소한의 방어력을 증가시켜 게임을 성공하는 것이 목적이다.

즉 방어구의 사용을 최소화 하고자 한다.

각 값들이 주어질 때, 게임을 성공하기 위하여 장비해야 할 방어구들의 방어력의 최솟값을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 $N, M, K, h$가 공백으로 구분되어 입력된다.
두 번째 줄에 $M$개의 방어구의 방어력들이 공백으로 구분되어 입력된다.
세 번째 줄부터 $N$줄에 걸쳐서 각 안전영역의 좌표 $x, y$가 공백으로 구분되어 입력된다.

[입력값의 정의역]
$1 ≤ N ≤ 3,000$
$1 ≤ M ≤ 20$
$1 ≤ K ≤ 3,000$
$0 ≤ h ≤ 1,000$
$1 ≤ 각 방어구의 방어력 ≤ 1,000$
$0 ≤ x, y ≤ 1,000$

Output

게임을 성공하기 위하여 주어진 방어구들 중 몇 개를 장착할 때, 이 방어력의 합의 최솟값을 출력한다. 만약 도달할 수 없다면 $-1$을 출력한다.

IO Example

입력
1 3 1 500
100 200 300
500 500

출력
500

* 설명

출발점$(0,0)$에서 $(500,500)$까지 가는데 데미지를 $1,000$ 받게 된다.

기본 체력이 5$00$이므로 방어구는 최소 $500$이상은 되어야 한다.

따라서 방어구들 중 $200 + 300$을 장착하면 안전영역1까지 갈 수 있고 그곳에서 엘릭서를 먹으면 다시 $HP$가 $1000$이 되어 목적지 $(1000, 1000)$ 까지 갈 수 있으므로 성공할 수 있는 최소 방어구들의 방어력의 합은 500이 된다.

입력2
1 3 1 499
100 200 300
500 500

출력2
600

* 이번에는 기본 체력이 $499$이고 적어도 $1000$의 데미지를 받아야 안전영역에 도달할 수 있으므로, 방어구 $100+200+300$으로 $600$이 되어야 안전영역으로 갈 수 있고, 엘릭서를 먹고 다시 도착지점으로 이동할 수 있다. 따라서 최소 방어력의 합은 $600$이 된다.

입력2
1 3 0 499
100 200 300
500 500

출력3
-1

* 아무리 방어구를 많이 장착하더라도, 도착점에 갈 수 없으며 안전영역1에 가더라도 엘릭서가 $0$개이므로 체력을 회복할 수 없다. 따라서 위 입력으로는 성공할 수 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]