All Right Editorial RDC 3

editorial
1

Problem Link:

Practice
Contest-Link

Author - Yash Dwivedi
Tester - Shubham Kushwaha
Editorialist - Yash Dwivedi

Difficulty :

Easy

PREREQUISITES:

Implementation

Problem :

You are given an array of integers and k moves. Your target is to maximize the rightmost element of the array. In one move you can choose an index i if a[i]>=2 and then replace a[i] by a[i]-2 and a[i+1] by a[i+1]+2.

Print the maximized value of the rightmost element of the array.

Explanation

If you apply brute force then it would take 0(nk) time to remove the k factor from the complexity
start the loop from the second last array and then if k>0 and i>=0 and the i-th element a[i]>=2, store the number of minimum chances in d then subtract k by d(n-i-1) i.e the number of chances you take for an index and then update the answer by d*2 . Print the final answer.

Solution

Setter's Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin>>t;
while(t–)
{
int n, k;
cin>>n>>k;

    int a[n];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }

    long long ans = a[n-1];

    for(int i=n-2; i>=0; i--)
    {
        long long d = min(a[i]/2, k/(n-1-i));
        k-=d*(n-1-i);
        ans+=d*2;
    }

    cout<<ans<<'\n';
}
return 0;

}