You can ask all 10 queries for 5 elements of the array. Let those element in sorted order be a,b,c,d,e. Let xi be sum of returned values in all queries in which ith element was involved. Sort them, Then, you can form 5 linear equations using the returned values.(6e+3a+2b+c=x5, 3e+3d+3a+2b+c=x4, 3e+2d+2c+3a+2b=x3, 3a+3b+3e+2d+c=x2, 6a+3e+2d+c=x1) If you solve those linear equations their solution is always unique for any xi. Thus, we can uniquely determine these 5 elements. Similarly, thus you can uniquely determine all of the elements for the constraints(n>=5).
My solution with precomputed inverse matrix of above linear equations 46821561

You are given an array of size N, now your task is two find two indices i and j such that i < j, A[i] < A[j], and A[i] * A[j] is as minimal as possible across all possible valid pairs. Since an O(N²) solution is straight forward, we will discuss how to solve this in O(N).

The final state of the answer is dependent on whether the answer is positive or negative, so we will split the answer in three cases, and solve individually for each.

Answer is negative, so A[i] * A[j] < 0 for optimally chosen i, and j. In this case, it is easy to solve as only one element can be negative, which follows that it must be A[i], since A[i] < A[j] from the problem conditions. Solving this is simple, we need to maintain a prefix minimum across all the array, then for every element A[i], it can contribute to the above case iff prefix_minimum[i] * A[i] < 0, then for all valid indices, we need to minimize the answer over prefix_minimum[i] * A[i], where prefix_min[i] is equal to minimum(prefix_minimum[i — 1], A[i]).

1. Answer is positive, with A[i] ≥ 0 and A[j] ≥ 0, for optimally chosen i, and j.

This case is easy to solve as well, for each element we just need to minimize over A[i] * prefix_min[i], if A[i] > prefix_min[i].

1. Answer is positive, with A[i] < 0 and A[j] < 0, for optimally chosen i, and j.

This is really the interesting case, since both numbers are negative, we should greedily try to multiply numbers with minimum absolute value. For example, multiplying -3 by -2, is more beneficial than say, multiplying -20 and -25, even though -3, and -2 are larger numbers. This makes the greedy approach used in case #1, and #2 fail to arrive at an optimal solution.

Let’s try to come with another strategy, we can notice that once a negative number A[j] appears in the array, it will never be beneficial to pair any element less than A[j] at position < j, with any element after j. More formally, Let’s denote our indices as i, j, and k, where i < j < k, A[i] < A[j], and A[i], A[j], A[k] < 0. Then, A[k] * A[j] < A[i] * A[k] for all k.

In another words, we should try and match each index with every non matched yet index to it’s left that is less than it. At first sight, this looks like O(N²), but with careful implementation we can achieve O(N) in amortized time. We will be using a monotone stack ( a stack where every value is increasing from bottom to top). Before we push an element to the stack, we keep popping every element less than it, and minimize over this pair, otherwise we stop, and push that element. We are essentially simulating the idea in the previous paragraph. This is a smart brute-force that combines greedy to only iterate over possibly interesting pairs.

Here’s a snippet: https://ideone.com/FxK16x

You still have to construct the array using a generator, here’s a spoiler on how to do it efficiently, you can use an unsigned int data type for your array.

Let's make a function f(x) that will tell us how many lections we can provide for each student in group of x students.

One of the possible optimal schedule patterns is greedy: fill empty slot in it with the number of student with least lections attended. Consider x = 6, n = 5, a = 5, b = 3: schedule is:

Day 1: 1 2 3 4 5
Day 2: 6 1 2
Day 3: 3 4 5 6 1
Day 4: 2 3 4
Day 5: 5 6 1 2 3

This way each student attends at least 3 lections. So f(6) = 3 in this case. We can show that result of this function is equal to , where slots is the sum of students capacity over all days. Note, that in case when a > x or b > x we cannot put more than x students in one day. So the final formula is:

This function is monotonic. f(v) ≤ f(u) for v > u. Now we can make a binary search over x to find maximum amount of students that each student can attend at least k lections.

Here's a puzzle for you: try to find the difference: 46856549 and then explain why this is significantly faster.

https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-team-russia-2018-presentation.pdf