Hướng dẫn giải

Các que được châm lửa ở đầu tự do trên đoạn ~[L, R]~; que đầu tiên cháy hết là que có ~b_i~ nhỏ nhất trong đoạn đó. Chỉ cần xác định thời điểm đó rồi tính thời gian cháy hết của từng que.

Sub 1: Tính lại mốc thời gian cho từng que — ~O(n^2)~, dùng khi ~n \le 5000~

Gọi ~m = \min(b_L, \ldots, b_R)~. Tại thời điểm ~m~, que nhỏ nhất cháy hết nên đầu buộc chung bị châm lửa, và từ đó mọi que còn lại đều bị đốt thêm ở đầu buộc. Với mỗi que ~i~, ta tính thời điểm nó cháy hết:

• Que ~i~ nằm trong ~[L, R]~ (đã cháy từ đầu tự do): đến thời điểm ~m~ còn ~b_i - m~, sau đó cháy hai đầu nên mất thêm ~(b_i - m)/2~, tổng cộng ~(m + b_i)/2~.
• Que ~i~ ngoài đoạn: chỉ bắt đầu cháy từ thời điểm ~m~ ở một đầu nên cháy hết lúc ~m + b_i~.

Đáp số là giá trị lớn nhất. Trong sub này, với mỗi que ta duyệt lại cả đoạn ~[L, R]~ để tìm ~m~. Kết quả luôn là bội của ~0.5~ nên nhân đôi lên để làm việc với số nguyên rồi in lại một chữ số thập phân. Nếu chỉ nộp sub này: đúng 9/11 test (2 test lớn bị quá giờ).

Sub 2: Tính ~m~ một lần — ~O(n)~

Giá trị ~m~ không phụ thuộc vào que đang xét nên chỉ cần tính một lần, sau đó duyệt qua các que để lấy giá trị lớn nhất. Nếu chỉ nộp sub này: đúng 11/11 test.

Chương trình hoàn chỉnh

Chương trình đọc ~n~, mảng ~b~ và hai số ~L, R~. Nếu ~n \le 5000~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chấm thử: chương trình đầy đủ đúng 11/11 test.

#include <bits/stdc++.h>
using namespace std;

int n, L, R;
long long b[100005];

// In kết quả từ giá trị nhân đôi v (kết quả luôn là bội của 0.5)
void in_ket_qua(long long v) {
    printf("%lld.%d\n", v / 2, v % 2 ? 5 : 0);
}

// Sub 1: với mỗi que, tính lại thời điểm m = min b[L..R] bằng vòng lặp — ~O(n^2)~
void sub1() {
    long long best = 0;
    for (int i = 0; i < n; i++) {
        long long m = LLONG_MAX;
        for (int j = L; j <= R; j++) m = min(m, b[j]);
        long long v;
        if (i >= L && i <= R) v = m + b[i];      // (m + b)/2 nhân đôi
        else v = 2 * (m + b[i]);                  // m + b
        best = max(best, v);
    }
    in_ket_qua(best);
}

// Sub 2: tính m một lần — ~O(n)~
void sub2() {
    long long m = LLONG_MAX, best = 0;
    for (int j = L; j <= R; j++) m = min(m, b[j]);
    for (int i = 0; i < n; i++) {
        long long v = (i >= L && i <= R) ? m + b[i] : 2 * (m + b[i]);
        best = max(best, v);
    }
    in_ket_qua(best);
}

int main() {
    freopen("MSTICK.INP", "r", stdin);
    freopen("MSTICK.OUT", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &b[i]);
    scanf("%d %d", &L, &R);
    if (n <= 5000) sub1();
    else sub2();
}