АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

         Танд n урттай 0 утгуудтай A массив байгаа. Уг массив дээр m удаа утга нэмж өгөх юм.

a b k ( A[a]+k, A[a+1]+k, A[a+2]+k …… A[b]+k ) а-гаас b хүртэлх массивын элементүүдийн утга дээр k-г нэмнэ.

Оролт :

3 ≤ n ≤ 10⁷

1 ≤ m ≤ 2*10⁵

1 ≤ a ≤ b ≤ n

0 ≤ k ≤ 10⁹

Гаралт :

Таны олох ёстой зүйл бол бүх утга нэмэгдсэний дараа массивын хамгийн их утгыг олох.

Жишээ :

Оролт :

10 3

1 5 3 

4 8 7

6 9 1

Гаралт:

10

Тайлбар:

    1 2 3 4 5 6 7 8 9 10            Дугаар:

[0,0,0, 0, 0,0,0,0,0, 0]

[3,3,3, 3, 3,0,0,0,0, 0]  (1,5)

[3,3,3,10,10,7,7,7,0, 0] (4,8)

[3,3,3,10,10,8,8,8,1, 0] (6,9)

Хамгийн их утга 10 байна.

Жишээ 1 :

Оролт :

5 3

1 2 100

2 5 100

3 4 100

Гаралт:

20

Тайлбар:

100 100   0     0     0

100 200 100 100 100

100 200 200 200 100

 Хамгийн их утга 200 байна.

Орчуулсан  : Дархан-Уул аймгийн Союз сургуулийн 12-р ангийн сурагч Б.Сумьяабазар