IOI 2013 day2 2- robots > 문제은행 : 정보올림피아드&알고리즘




1999 : robots

제한시간
3000 ms   
메모리제한
256 MB   
해결횟수
2 회   
시도횟수
3 회   

문제

마리타의 남동생은 모든 장난감을 거실 바닥에 어질러놓았다! 

다행히도 마리타는 장난감을 정리하는 특별한 로봇들을 개발하였다. 

마리타는 어떤 로봇이 어떤 장난감을 집어야 하는지 결정하도록 당신에게 도움을 청했다.

 

장난감은 총 T 개가 있으며, 각각은 정수 무게 W[i] 와 정수 크기 S[i]를 가진다. 

로봇들은 연약한 로봇과 작은 로봇 두 가지 종류가 있다.

 

⚫ 연약한 로봇은 총 A 개가 있다. 각 연약한 로봇에는 무게 제한 X[i] 가 있어서, 
X[i] 미만의 무게를 가진 장난감만을 운반할 수 있다. 장난감의 크기는 상관없다.
⚫ 작은 로봇은 총 B 개가 있다. 각 작은 로봇에는 크기 제한 Y[i] 가 있어서, 
Y[i] 미만의 크기를 가진 장난감만을 운반할 수 있다. 장난감의 무게는 상관없다.

 

마리타의 로봇들 각각은 하나의 장난감을 정리하는 데 1분이 걸린다. 

여러 로봇들이 서로 다른 장난감들을 동시에 정리할 수 있다.

 

당신의 임무는 마리타의 로봇들이 모든 장난감들을 정리할 수 있는지 결정하고, 

만약 가능하다면, 모든 장난감을 정리하는데 걸리는 가장 짧은 시간을 찾는 것이다.

 

첫 번째 예시로, 무게 제한 X = [6, 2, 9]를 가진 A = 3 개의 연약한 로봇과 크기 제한 Y = [4, 7] 을 가진 B = 2 개의 작은 로봇이 있고, 

T = 10 개의 장난감이 아래와 같이 있다고 하자:

 

 

모든 장난감들을 정리하는 데 걸리는 가장 짧은 시간은3분이다:

 

 

 

 

두 번째 예시로, 무게 제한 X = [2, 5] 를 가진 A = 2 개의 연약한 로봇과 크기 제한 Y = [2] 를 가진 B = 1 개의 작은 로봇이 있고, 

T = 3 개의 장난감이 아래와 같이 있다고 하자:

 

 

 

 어떤 로봇도 무게 5, 크기 3짜리의 장난감을 정리할 수 없기 때문에, 모든 장난감들을 치우는 것은 불가능하다.

 

 

<제약조건>
⚫ 1 ≤ T ≤ 1,000,000
⚫ 0 ≤ A, B ≤ 50,000 및 1 ≤ A + B
⚫ 1 ≤ X[i], Y[i], W[i], S[i] ≤ 2,000,000,000

 

 


[서브태스크]
서브태스크 1 : T = 2 및 A + B = 2 (정확히 두 개의 장난감 및 두 개의 로봇)
서브태스크 2 : B = 0 (모든 로봇이 연약함)
서브태스크 3 : T ≤ 50 및 A + B ≤ 50
서브태스크 4 : T ≤ 10,000 및 A + B ≤ 1,000
서브태스크 5 : (없음)

 


입력형식

line 1: 연약한 로봇의 수 A, 작은 로봇의 수 B, 장난감의 개수 T가 공백으로 구분하여 들어온다.

line 2: 연약한 로봇의 무게 제한이 A개 들어온다. (X[0] … X[A-1]) 

line 3: 작은 로봇의 크기 제한이 B개 들어온다. (Y[0] … Y[B-1]) 

이상 lines : 장난감의 무게 W, 크기 S가 공백으로 구분하여 들어온다.


출력형식

출력의 첫 줄에 모든 장난감을 정리하는 데 걸리는 가장 짧은 시간을 출력한다.

불가능한 경우 –1을 출력한다.


입력 예

3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5

출력 예

3

입력 예

2 1 3
2 5
2
3 1
5 3
2 2

출력 예

-1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP