시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 288 | 110 | 87 | 41.038% |
소들은 밥을 먹을 때 친구들과 가까이 줄을 선다. 선영이는 소를 N마리 (2 ≤ N ≤ 1,000 가지고 있고, 1번부터 N번까지 번호를 붙였다. 소는 일직선으로 번호 순으로 줄을 서서 밥을 기다린다. 이때, 두 마리 이상의 소가 같은 위치에 서는 것도 가능하다. 같은 좌표를 갖는 소가 두 마리 이상일 수도 있다.
서로를 좋아하는 소는 특정 거리 이내에 서 있으려고 한다. 그리고 서로를 싫어하는 소는 특정 거리 이상 떨어지려고 한다. 어떤 소들이 서로를 좋아하는지와 두 소가 최대한 떨어질 수 있는 거리가 길이가 ML(1 ≤ ML ≤ 10,000)인 리스트로 주어진다. 다음으로 어떤 소들이 서로를 싫어하는지와 두 소가 최소한 떨어져야 하는 거리가 MD(1 ≤ MD ≤ 10,000) 길이의 리스트로 주어진다.
위 조건을 만족하면서 줄을 서는 것이 가능하다면, 1번 소와 N번 소의 최대 거리를 구하는 프로그램을 작성하시오.
입력의 첫째 줄에는 정수 N, ML, MD가 공백으로 구분되어 주어진다.
둘째 줄부터 ML+1번째 줄까지 양의 정수 A, B, D (1 ≤ A < B ≤ N)가 공백으로 구분되어 주어진다. 소 A와 소 B는 최대한 D (1 ≤ D ≤ 1,000,000)만큼 떨어질 수 있다.
ML+2번째 줄부터 ML+MD+1번째 줄까지 양의 정수 A, B, D (1 ≤ A < B ≤ N)이 공백으로 구분되어 주어진다. 소 A와 소 B는 최소한 D (1 ≤ D ≤ 1,000,000)만큼 떨어져 있어야 한다.
첫째 줄에 1번 소와 N번 소의 최대 거리를 출력한다. 줄을 서는 것이 불가능한 경우에는 -1을 출력한다. 1번 소와 N번 소의 최대 거리가 무한대인 경우에는 -2를 출력한다.
4 2 1 1 3 10 2 4 20 2 3 3
27
Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO December 2005 Contest > Gold 3번