Bedao Regular Contest 08 - FUNFAIR

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Nhân dịp cuối năm được học sinh giỏi, illya được mẹ dẫn đi gian hàng hội chợ. Bước vào một quầy bắn cung, có ~n~ quả bóng bay được đính trên tường xếp thành một hàng ngang, mỗi quả bóng đều được dán lên một số điểm, lần lượt từ trái sang phải, quả bóng thứ nhất có số điểm là ~a_1~, quả bóng thứ hai có số điểm là ~a_2~, ~\dots~, quả bóng thứ ~n~ có số điểm là ~a_n~. Để làm khó người chơi, người chủ quầy quy định rằng các quả bóng mà illya bắn phải nằm liên tiếp nhau và quả bóng có số điểm ít nhất trong những quả bóng mà illya bắn phải có giá trị từ ~x~ đến ~y~. Để nhận được phần thưởng, illya phải bắn những quả bóng và giành được điểm số cao nhất có thể. Hãy giúp illya đạt được phần thưởng nhé!

Input

  • Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 10^6)~, là số quả bóng bay được dính trên tường.
  • Dòng thứ hai chứa hai số nguyên ~x~ và ~y~ ~(-10^9 \leq x \leq y \leq 10^9)~.
  • Dòng thứ ba chứa ~n~ số nguyên ~a_1~, ~a_2~, ~\dots~, ~a_n~ ~(-10^9 \leq a_i \leq 10^9)~.

Output

  • Dòng đầu tiên chứa một số nguyên là số điểm lớn nhất thỏa mãn yêu cầu đề bài.
  • Dòng thứ hai chứa hai số nguyên ~l~ và ~r~ ~(1 \leq l \leq r \leq n)~ là chỉ số của quả bóng thứ ~l~ và quả bóng thứ ~r~, mô tả danh sách các quả bóng có tổng điểm lớn nhất thỏa mãn yêu cầu đề bài. Dữ liệu vào đảm bảo có ít nhất một danh sách thỏa mãn. Nếu có nhiều danh sách các quả bóng cho ra điểm lớn nhất, bạn được in ra một phương án bất kì.

Subtask

  • Có ~20\%~ số test là ~1 \leq n \leq 100~
  • Có ~20\%~ số test là ~1 \leq n \leq 5000~
  • Có ~30\%~ số test là ~1 \leq n \leq 2 \times 10^5~
  • Có ~30\%~ số test là ~1 \leq n \leq 10^6~

Sample Input 1

7 
6 30
9 27 4 20 8 13 50

Sample Output 1

91
4 7

Sample Input 2

7
1 5
1 4 2 6 6 2 7

Sample Output 2

28
1 7

Comments

Please read the guidelines before commenting.



  • 4
    nguyenhuunhan   commented on Aug. 22, 2022, 10:16 p.m.

    Hình như bộ test của bài hơi yếu, bài của mình tuy bỏ luôn điều kiện a[i] <=y nhưng vẫn đc hơn 75% test