Bedan Contest #04 - C - Tiền lì xì

View as PDF

Submit solution

Points: 1600 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: lixi.inp
Output: lixi.out

Author:
Problem types
Allowed languages
C++, NASM, Pascal, pypy3, Python

Nên nhớ là có đọc tên file đấy

Trong những ngày Tết, tiền lì xì là một thứ không thể thiếu đối với những bạn nhỏ và hầu như bạn nào cũng thích. Mặc dù đã ăn 14 nồi bánh chưng nhưng mỗi khi Tết đến, flo lại vô cùng háo hức khi được nhận tiền lì xì và năm nay cũng như vậy.

Hôm nay, flo đến nhà của bác mình là huyhau6a2 để chơi. Nhắc tới huyhau6a2, mọi người đều biết đến bác là một người siêu giàu khi sở hữu 69 căn biệt thự siêu to khổng lồ và 420 món đồ mua từ shop Thái Công. Thấy người cháu của mình đến chơi, bác huyhau6a2 liền đem ra cho flo n phong bì lì xì với phong bì thứ i sẽ có a_i đồng. Để thêm phần thử thách, bác huyhau6a2 muốn flo chia n phong bì trên thành k dãy phong bì liên tiếp khác nhau. Khi số, số tiền lì xì flo nhận được sẽ là tích của tổng từng dãy phong bì trong k dãy trên.

Nhận thấy đây là cơ hội làm giàu, flo quyết định chấp nhận thử thách của bác huyhau6a2 đặt ra. Tuy nhiên, cậu không biết phải chia n phong bì trên như thế nào để số tiền cậu nhận được là lớn nhất có thể. Bạn hãy tính giúp flo nhé.

Lưu ý rằng trong mỗi cách chia, mỗi phong bì chỉ được thuộc duy nhất 1 dãy phong bì lì xì.

Input, Output and Scoring

Input (lixi.inp)
  • 2 số nguyên dương n, k (1 \le k \le n \le 200).
  • Dãy a gồm n phần tử a_1, a_2, ..., a_n (1 \le a_i \le n).
Output (lixi.out)
  • In ra k dòng, dòng thứ i1 cặp số (l, r) nghĩa là dãy phong bì thứ i sẽ chứa các phong bì từ vị trí l đến r.
  • Nếu có nhiều cách chia có cùng số tiền lớn nhất, hãy in ra một cách chia bất kỳ.
Scoring
  • Subtask 1 (10\%): k = 2.
  • Subtask 2 (30\%): 1 \le k \le n \le 20.
  • Subtask 3 (60\%): Không giới hạn gì thêm.

Test 1

Input (lixi.inp)
5 3
2 3 1 4 2     
Output (lixi.out)
1 2
3 4
5 5
Note
  • Khi chia như trên, flo sẽ nhận được số tiền lì xì lớn nhất là 50.

Test 2

Input (lixi.inp)
3 2
1 1 1    
Output (lixi.out)
1 2
3 3
Note
  • Cách chia (1, 1)(2, 3) cũng sẽ nhận được số tiền lì xì là 2 như trên.

Comments

There are no comments at the moment.