Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

Aspergillus's blog

By Aspergillus, history, 6 weeks ago,

Given an array, you can pick exactly $x$ (where $x \leq 3$) elements in one operation and decrease each of them by 1 (all picked elements must be at least 1). You then add $x$ points to your score. You need to maximize your points with these operations applied any number of times as long as it is possible.

I think you could use a priority queue to greedily pick the top $x$ largest elements and decrease them by 1, but the problem is that the elements can go up to $10^{16}$.

Also, the length of the array is at most 200.

• 0

 » 6 weeks ago, # |   0 If you pick a element you add a point , if you pick two you add two points if you pick three elements you add 3 points.But you decrease 1 , 2, respectively 3 vals by 3 , so if we consider the whole sum of the array you decrease the sum by 1 you increase ans by 1 so that wouldnt actually mean that the ans is the sum of the array?
•  » » 6 weeks ago, # ^ |   0 No because x is given as input. We have to pick exactly x elements at once.
 » 6 weeks ago, # | ← Rev. 3 →   0 max_points = sum(array)
•  » » 6 weeks ago, # ^ |   0 no
 » 6 weeks ago, # | ← Rev. 2 →   0 Is it not just the sum of the array? You just decrease all elements of the array to 0 by picking x=1.
 » 6 weeks ago, # |   0 If you MUST pick x elements, x is given in the input.if x == 1: answer = sum(array)if x == 2: Consider cases like [2, 5] and x = 2. The answer should be 4. find the max and set it to min(mx, rest_sum(excluding max)). answer = new_sum — new_sum % 2if x == 3: consider cases like [1 3 5 7] and x = 3. The answer should be 12. save the max of the array and remove it from the array. Modify the array as shown in x = 2 for the new array. Then set the saved max to min(new_sum / 2, max). sum = modified_max + new_sum. answer = sum — sum % 3.I think you can extend this for arbitrary 'x'
•  » » 6 weeks ago, # ^ |   0 You mean this? Code:#include using namespace std; using i64 = long long; void solve() { int n; cin >> n; vector a (n); for (int i = 0; i < n; ++i) cin >> a[i]; int x; cin >> x; sort(a.begin(), a.end()); int s = accumulate(a.begin(), a.begin() + n - x + 1, 0); for (int i = n + 1 - x; i < n; ++i) { a[i] = min(a[i], s / (x - n + i)); s += a[i]; } cout << s - s % x << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; } 
 » 6 weeks ago, # | ← Rev. 5 →   0 Decrement the x picked elements by the minimum of the x picked elements. Increment the ans by x*(minimum of the x picked elements).If any of the elements after decrementing are still positive, then only push them back into the heapIf sizeof(heap) become less than x then terminateOr we can merge the minimum of the x picked element with the other smaller elements till it is less than equal to 2nd minimum element of the x picked elementse.g., arr[12,11,6,4] and x=3ans=6*3 + 4*3 i.e., 30after above operation it will reduce the number of operations to be performed arr[12,11,10]ans= 10*3 i.e., 30if there are other smaller elements add them to the minimum till it is less than equal to 2nd min
•  » » 6 weeks ago, # ^ |   0 Your solution doesn't work for example in 4 4 4 4 and x = 3, you pick the first three 4s. Your array becomes 0 0 0 4, and your answer 12. However we can go upto 15. Another example, 2 2 2, x = 2, your answer is 4 but it can go to 6.
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by Aspergillus (previous revision, new revision, compare).