문제 설명
아래 그림과 같이 직선 형태의 도로상에 왼쪽부터 오른쪽으로 \(1\)번부터 \(N\)번까지 번호가 붙어 있는 \(N\)개의
집이 있다. \(i (1 \le i \le N)\)번 집의 위치는 \(X_i (X_i > 0)\)이다.
택배 회사는 한 대의 트럭을 이용해 \(N\)개의 집을 방문하면서 반품되는 물건을 회수하려고 한다. 트럭은
택배 회사가 있는 위치 0에서 시각 0에 출발하고, \(i\)번 집은 시각 \(T_i\)에 반품할 물건을 내놓는다. 트럭은 1의
속력으로 이동하므로, \(d\)만큼의 거리를 이동하는데 \(d\) 시간이 걸린다. 또한, 트럭은 필요하면 움직이지 않고
제자리에 멈춰서 기다릴 수 있다.
트럭은 반품할 물건이 나와있는 집의 위치를 지나면 순식간에 물건을 회수할 수 있다. 즉, 물건을 회수하는 데 소요되는 시간은 0이다. 따라서 트럭은 위치 \(X_i\)를 시각 \(T_i\) 또는 그 이후에 지나면 \(i\)번 집에서 내놓은 물건을 회수할 수 있다.
직선 형태의 도로 위에 있는 집의 위치와 반품할 물건을 내놓는 시각이 주어질 때, 트럭이 모든 물건을 회수해서 다시 택배 회사로 돌아오는 데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하라.
제약 조건
• 주어지는 모든 수는 정수이다.
• \(1 \le N \le 3 000\)
• \(1 \le X_1 \le X_2 < · · · < X_N ≤ 10^8\)
• \(0 \le T_i \le 10^8 (1 \le i \le N)\)
부분문제
1. (10점) \(N = 2\)
2. (15점) \(N \le 9\)
3. (5점) 모든 \(1 \le i \le N\)에 대해 \(T_i = 0\)
4. (25점) 모든 \(2 \le i \le N\)에 대해 \(T_{i−1} \le T_i\)
5. (45점) 추가 제약 조건 없음
트럭은 반품할 물건이 나와있는 집의 위치를 지나면 순식간에 물건을 회수할 수 있다. 즉, 물건을 회수하는 데 소요되는 시간은 0이다. 따라서 트럭은 위치 \(X_i\)를 시각 \(T_i\) 또는 그 이후에 지나면 \(i\)번 집에서 내놓은 물건을 회수할 수 있다.
직선 형태의 도로 위에 있는 집의 위치와 반품할 물건을 내놓는 시각이 주어질 때, 트럭이 모든 물건을 회수해서 다시 택배 회사로 돌아오는 데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하라.
제약 조건
• 주어지는 모든 수는 정수이다.
• \(1 \le N \le 3 000\)
• \(1 \le X_1 \le X_2 < · · · < X_N ≤ 10^8\)
• \(0 \le T_i \le 10^8 (1 \le i \le N)\)
부분문제
1. (10점) \(N = 2\)
2. (15점) \(N \le 9\)
3. (5점) 모든 \(1 \le i \le N\)에 대해 \(T_i = 0\)
4. (25점) 모든 \(2 \le i \le N\)에 대해 \(T_{i−1} \le T_i\)
5. (45점) 추가 제약 조건 없음
입력 설명
첫 번째 줄에 반품할 물건을 내놓을 집의 개수 \(N\)이 주어진다.
두 번째 줄에 각 집의 위치 \(X_1, X_2, · · · , X_N\)이 공백으로 구분되어 주어진다.
세 번째 줄에 각 집이 물건을 내놓는 시각 \(T_1, T_2, · · · , T_N\)이 공백으로 구분되어 주어진다.
두 번째 줄에 각 집의 위치 \(X_1, X_2, · · · , X_N\)이 공백으로 구분되어 주어진다.
세 번째 줄에 각 집이 물건을 내놓는 시각 \(T_1, T_2, · · · , T_N\)이 공백으로 구분되어 주어진다.
출력 설명
첫 번째 줄에 트럭이 모든 물건을 회수하고 다시 택배 회사로 돌아오기 위해 필요한 시간의 최솟값을
출력한다.
입력 예시 Copy
4
2 5 7 10
20 4 16 11
출력 예시 Copy
23
도움
초3,고1