k altmassivə bölünmə#9020
elementdən ibarət massiv və ədədi verilmişdir. Bu massivi bütün elementləri istifadə edərək altmassivə bölün (elementlərin sırası qorunur, hər bir element tam olaraq bir altmassivə daxil edilməlidir).
Hər bir bölünmə üçün altmassivin elementlərinin cəmlərinin maksimumu hesablanır. Bölünməni elə aparmaq lazımdır ki, bu maksimum mümkün qədər az olsun. Bu minimal mümkün qiyməti tapın.
Birinci sətir iki tam ədəd olan və k~(1 \le k \le n \le 10^6) ədədlərini ehtiva edir.
İkinci sətir massiv elementləri olan təbii ədəd ehtiva edir. Hər bir ədəd 10^9-u keçmir.
Massivin altmassivə bölünməsi zamanı mümkün olan maksimum cəmin ən kiçik dəyərini çap edin.
Birinci nümunə üçün optimal bölünmə \{1, 2\}, \{3\}, \{4\} olacaq. Altmassivlərin cəmləri: , , . Onların maksimumu -dür və bu, k = 3 üçün mümkün olan ən kiçik dəyərdir.
İkinci nümunə üçün optimal bölünmə \{1, 2, 3, 4\}, \{2, 3, 4\}, \{2, 3, 1\} olacaq. Altmassivlərin cəmləri: , , . Onların maksimumu olan - bu k = 3 üçün mümkün olan ən kiçik dəyərdir.
Nümunə 1
Nümunə 2