Anna làm việc cho một công viên giải trí và được giao xây dựng đường ray cho một tàu lượn cao tốc mới. Cô đã thiết kế \(n\) đoạn đường đặc biệt, đánh số từ \(0\) đến \(n-1\), có tác động đến tốc độ của tàu. Bây giờ cô cần ghép chúng thành đường ray hoàn chỉnh. Trong bài toán này, có thể coi chiều dài của đoàn tàu bằng không.

Đoạn đường đặc biệt \(i\) có hai tính chất:

• Khi đi vào đoạn đường, tốc độ của tàu phải không vượt quá \(s_i\) km/h.
• Khi đi ra, tốc độ của tàu đúng bằng \(t_i\) km/h, không phụ thuộc tốc độ lúc đi vào.

Đường ray hoàn chỉnh gồm tất cả \(n\) đoạn đường đặc biệt theo một thứ tự nào đó, mỗi đoạn được dùng đúng một lần. Hai đoạn liên tiếp được nối bằng một đoạn ray có độ dài là số nguyên không âm, tính bằng mét. Anna cần chọn thứ tự các đoạn đặc biệt và độ dài các đoạn ray nối.

Mỗi mét ray nối làm tốc độ của tàu giảm đi \(1\) km/h. Tàu bắt đầu đi vào đoạn đường đặc biệt đầu tiên với tốc độ \(1\) km/h. Thiết kế phải bảo đảm tàu không vi phạm giới hạn tốc độ đầu vào của bất kỳ đoạn đặc biệt nào và tốc độ luôn dương.

Trong mọi subtask trừ subtask \(3\), hãy tìm tổng độ dài nhỏ nhất có thể của các đoạn ray nối. Trong subtask \(3\), chỉ cần xác định có thể thiết kế sao cho mọi đoạn ray nối đều dài \(0\) hay không.

Chi tiết cài đặt

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

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t);

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

public static long plan_roller_coaster(int[] s, int[] t)

Trong C, giao diện là:

long long plan_roller_coaster(int n, int* s, int* t);

• s, t: hai mảng độ dài \(n\), lần lượt chứa giới hạn tốc độ đầu vào và tốc độ đầu ra của các đoạn đặc biệt.
• Trong C, n là số phần tử của mỗi mảng.
• Trong mọi subtask trừ subtask \(3\), trả về tổng độ dài nhỏ nhất của các đoạn ray nối, bằng số nguyên \(64\) bit.
• Trong subtask \(3\), trả về \(0\) nếu có thiết kế mà mọi đoạn ray nối đều dài \(0\); nếu không, trả về một số nguyên dương bất kỳ. Trả về tổng độ dài nhỏ nhất vẫn thỏa mãn yêu cầu này.

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 "railroad.h" thay cho #include "railroad_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 200\,000\).
• \(1 \le s_i \le 10^9\) và \(1 \le t_i \le 10^9\), với mọi \(0 \le i < n\).

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. Giới hạn \(1 \le s_i,t_i \le 10^9\) áp dụng cho mọi subtask.

Ví dụ

plan_roller_coaster([1, 4, 5, 6], [7, 3, 8, 6])

Một thiết kế tối ưu dùng các đoạn đặc biệt theo thứ tự \(0,3,1,2\), với các đoạn ray nối dài lần lượt \(1,2,0\) mét:

1. Tàu đi vào đoạn \(0\) với tốc độ \(1\) km/h và đi ra với tốc độ \(7\) km/h.
2. Đi qua \(1\) mét ray nối, tốc độ giảm còn \(6\) km/h. Tàu đi vào đoạn \(3\) và đi ra với cùng tốc độ.
3. Đi qua \(2\) mét ray nối, tốc độ giảm còn \(4\) km/h. Tàu đi vào đoạn \(1\) và đi ra với tốc độ \(3\) km/h.
4. Tàu đi ngay vào đoạn \(2\) qua đoạn ray nối dài \(0\), rồi đi ra với tốc độ \(8\) km/h.

Tổng độ dài các đoạn ray nối là

Do đó hàm trả về \(3\).

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa \(n\). Dòng \(2+i\), với \(0 \le i < n\), chứa \(s_i,t_i\). Trình chấm mẫu in giá trị trả về của plan_roller_coaster trên một dòng.

4
1 7
4 3
5 8
6 6

3

Nguồn

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