Valentine's Day '19 S3 - Mathematical English

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Java 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are reading a novel in English class! The novel has a total of N chapters, with each chapter consisting of p_i pages. Your teacher has broken up your class into M groups, each with g_j students, for presentations.

He wants to assign a potentially empty subarray of the chapters to each group for them to present, such that each chapter is assigned to exactly one group. Note that chapters can not be split.

Your teacher defines s_j = \bigg\lceil\frac{p_{x_j} + p_{x_j+1} +\cdots + p_{y_j}}{g_j} \bigg\rceil for all 1 \le j \le M. That is, s_j is the number of pages each student in group j receives, given that group j is assigned the subarray of chapters [x_j, y_j], rounded up. If group j is assigned an empty subarray of chapters, then s_j = 0.

Since students these days care all about fairness, they will protest if their group receives more pages per student than some other group. As such, your teacher wants to assign the chapters in such a way as to minimize \max{s_j} for all 1 \le j \le M. That is, he wants to minimize the maximum number of pages per student out of all the groups.

However, your teacher is not that good at math, so he wants you to tell him, if he assigns the chapters optimally, what is the minimum of \max{s_j} for all 1 \le j \le M he can achieve?

Input Specification

The first line will contain two integers, N, M\ (1 \le N \le 10^5, 1 \le M \le 8).

The second line will contain N integers, p_1, p_2, \ldots, p_N\ (1 \le p_i \le 10^9).

The third line will contain M integers, g_1, g_2, \ldots, g_M\ (1 \le g_j \le 10^9).

Output Specification

Print the minimum of \max s_j for all 1 \le j \le M if the chapters were assigned optimally, such that every group is assigned a potentially empty subarray of chapters, and every chapter is assigned to exactly one group.


Subtask 1 [5%]

N \le 10^3, M \le 3

Subtask 2 [15%]

N \le 10^3, M \le 4

Subtask 3 [30%]

N \le 10^5, M \le 5

Subtask 4 [50%]

No further constraints.

Sample Input 1

5 3
1 3 2 4 3
2 3 2

Sample Output 1


Explanation For Sample 1

Group 1 can be assigned the subarray [4,4].

s_1 = 2

Group 2 can be assigned the subarray [1,3].

s_2 = \frac{1+3+2}{3} = 2

Group 3 can be assigned the subarray [5,5].

s_3 = \big\lceil\frac{3}{2}\big\rceil = 2

Sample Input 2

5 4
1 2 5 7 10
3 2 2 1

Sample Output 2



There are no comments at the moment.