Pavel có một bộ đồ chơi đường sắt. Đường chính gồm \(n\) trạm, được đánh số từ \(0\) đến \(n-1\) theo thứ tự dọc đường. Khoảng cách giữa trạm \(i\) và \(i+1\) là \(l_i\) cm, với \(0 \le i < n-1\).

Ngoài đường chính có thể có một số đường nhánh. Mỗi đường nhánh nối một trạm trên đường chính với một trạm mới không nằm trên đường chính. Các trạm mới không được đánh số. Từ mỗi trạm trên đường chính có nhiều nhất một đường nhánh. Đường nhánh xuất phát từ trạm \(i\) dài \(d_i\) cm; \(d_i=0\) biểu thị rằng không có đường nhánh từ trạm đó.

Pavel dự định xây một đường tắt nối hai trạm khác nhau trên đường chính. Hai trạm này có thể kề nhau. Đường tắt luôn dài đúng \(c\) cm, bất kể hai trạm được chọn.

Mọi đoạn đường sắt, kể cả đường tắt mới, đều có thể đi theo cả hai chiều. Khoảng cách giữa hai trạm là độ dài ngắn nhất của một tuyến đường nối chúng dọc theo mạng đường sắt. Đường kính của mạng là khoảng cách lớn nhất giữa mọi cặp trạm, bao gồm cả các trạm ở cuối đường nhánh. Tương đương, đó là số nhỏ nhất \(t\) sao cho khoảng cách giữa bất kỳ hai trạm nào cũng không vượt quá \(t\).

Hãy tìm đường kính nhỏ nhất có thể sau khi Pavel xây đường tắt.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong shortcut.h:

long long find_shortcut(int n, std::vector <int> l, std::vector <int> d, int c);

Trong Java, cài đặt phương thức sau trong lớp shortcut:

public long find_shortcut(int n, int[] l, int[] d, int c)

Trong C, giao diện là:

long long find_shortcut(int n, int* l, int* d, int c);

• n: số trạm trên đường chính.
• l: mảng độ dài \(n-1\) chứa độ dài các đoạn đường chính.
• d: mảng độ dài \(n\) chứa độ dài các đường nhánh, hoặc \(0\) nếu không có nhánh.
• c: độ dài đường tắt mới.
• Hàm trả về đường kính nhỏ nhất sau khi thêm đường tắt, bằng số nguyên \(64\) bit.

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "shortcut.h" thay cho #include "shortcut_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(2 \le n \le 1\,000\,000\).
• \(1 \le l_i \le 10^9\), với \(0 \le i < n-1\).
• \(0 \le d_i \le 10^9\), với \(0 \le i < n\).
• \(1 \le c \le 10^9\).

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Các giới hạn chung đối với \(l_i,d_i,c\) áp dụng cho mọi subtask.

Ví dụ

Lời gọi thứ nhất tương ứng với mạng đường sắt ở hình trên:

find_shortcut(4, [10, 20, 20], [0, 40, 0, 30], 10)

Phương án tối ưu nối trạm \(1\) và trạm \(3\) như hình sau. Đường kính của mạng mới là \(80\) cm, nên hàm trả về \(80\).

Lời gọi thứ hai:

find_shortcut(9, [10, 10, 10, 10, 10, 10, 10, 10], [20, 0, 30, 0, 0, 40, 0, 40, 0], 30)

Nối trạm \(2\) và \(7\) là tối ưu; hàm trả về \(110\).

Lời gọi thứ ba:

find_shortcut(4, [2, 2, 2], [1, 10, 10, 1], 1)

Nối trạm \(1\) và \(2\) là tối ưu, làm đường kính giảm còn \(21\). Hàm trả về \(21\).

Lời gọi thứ tư:

find_shortcut(3, [1, 1], [1, 1, 1], 3)

Nối bất kỳ hai trạm nào bằng đường tắt dài \(3\) cũng không cải thiện đường kính ban đầu là \(4\). Hàm trả về \(4\).

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): \(n,c\).
• Dòng \(2\): \(l_0,l_1,\ldots,l_{n-2}\).
• Dòng \(3\): \(d_0,d_1,\ldots,d_{n-1}\).

Trình chấm mẫu in giá trị trả về của find_shortcut trên một dòng.

4 10
10 20 20
0 40 0 30

80

9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0

110

4 1
2 2 2
1 10 10 1

21

3 3
1 1
1 1 1

4

Nguồn

IOI 2016, ngày thi thứ nhất, bài Shortcut. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.