문제
어느 학교에 두 말썽꾸러기 창하와 재하가 다니고 있다. 이 둘은 항상 교실을 어질러 놓고 물건을 제자리에 안 놓으며 숙제를 제때 하지 않는 것으로 유명하다.
존경 받아 마땅한 훌륭한 명선생님인 택쌤은 창하와 재하의 참된 교육을 위하여, 이 둘에게 할 일들의 목록을 주고, 모두 행하도록 하였다.
창하와 재하에게는 N개의 할 일이 있으며, 하나의 할 일은 아래의 세 종류 중 하나이다.
- 반드시 창하가 해야 하는 일
- 반드시 재하가 해야 하는 일
- 창하 또는 재하 둘 중 한 명이 하면 되는 일.
창하와 재하 둘 중 한 명이 하면 되는 일의 경우, 창하가 할 때 걸리는 시간과 재하가 할 때 걸리는 시간이 각각 다를 수도 있다.
N개의 일을 반드시 순서대로 할 필요는 없으며, 한 명이 하나의 일을 하는 동안, 다른 한 명이 다른 일을 하고 있어도 상관없다.
창하와 재하가 해야 N개의 일에 대한 시간 정보가 주어졌을 때, 이를 모두 끝내는데 걸리는 최소시간을 출력하는 프로그램을 작성하라.
입력
첫 줄에 N이 주어진다.
다음 N개의 줄에 각 할 일별로 창하가 행할 때 걸리는 시간 pi와 재하가 행할 때 걸리는 시간 qi가 공백을 사이에 두고 주어진다.
반드시 재하가 해야 하는 일이라면, 창하의 수행시간 pi는 -1로 주어지며, 반드시 창하가 해야 하는 일이라면 재하의 수행시간 qi는 -1로 주어진다.
(1≤N≤500,1≤pi≤200 또는 pi=-1, 1≤qi≤200 또는 qi=-1)
(당연히)어떤 일에 대해서도 pi=-1이고 qi=-1인 경우는 없다.
출력
창하와 재하가 모든 일을 끝내는데 걸리는 시간의 최솟값을 출력한다.
부분문제 1)(2점)
부분문제 2)(6점)
부분문제 3)(6점)
부분문제 4)(22점)
부분문제 5)(64점)
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 2점 | 모든 일에 있어서 pi=-1이거나 qi=-1이다. |
| #2 | 6점 | N≤10을 만족한다. |
| #3 | 6점 | N≤50이고 전체 일의 80% 이상은 pi=-1이거나 qi=-1이다. |
| #4 | 22점 | N≤50, pi≤50, qi≤50이다. |
| #5 | 64점 | 주어진 제약 조건 외에 아무 제약조건이 없다. |
예제 #1
3
2 5
4 5
6 5
6
예제 #2
5
-1 6
7 -1
5 3
2 8
9 8
14
첫 번째와 마지막 일을 재하가 하고 나머지 3개의 일을 창하가 하는 것이 최적이다.
로그인해야 코드를 작성할 수 있어요.