HMWPRB - Editorial

Thankyou for your answer

Thank you for the details.

sorry , actually I saw on a stream the guy was using long long and got RTE , so felt u did the same

nice u r using gdb right , its being taught in our current semester
some other tools like valgrind , gcov and gprof are helpful too , but gdb alone is sufficient

can anyone tell why the solution is giving RE with array but AC by using vector
#include <bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ll long long int
#define f(i, n) for (ll i = 0; i < n; i++)
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin >> t;
while (t–)
{
ll n, k;
cin >> n >> k;
ll arr[n] = {0};
f(i, n)cin >> arr[i];
if (k >= n)
{
cout << 0 << “\n”;
}
else
{
ll dp[n];
deque<pair<ll,ll>> dq; //storing the index of dp in increasing order to get minimin in k + 1 elements
f(i, k + 1)
{
dp[i] = arr[i];
while (!dq.empty() && dq.back().first > dp[i])
{
dq.pop_back();
}
dq.push_back({dp[i],i});
}
for (int i = k + 1; i < n; i++)
{
if (dq.front().second < i - k - 1)
{
dq.pop_front();
}
dp[i] = arr[i] + dq.front().first;
while (!dq.empty() && dq.back().first > dp[i])
{
dq.pop_back();
}
dq.push_back({dp[i],i});
}
ll ans;
while(dq.front().second < n- 1 - k){
dq.pop_front();
}
ans = dq.front().first;
cout << ans << “\n”;
}
}
}

To calculate the minimum value in a range of size (k+1) , we can use greedy approach only no need for dequeue.
My solution

This solution gave TLE. I am not sure why. Is it because of the array?

        ll int sum=0;
	    for(ll int left=index; left>0; left-k) // Here
	    {
	        sum = sum + inputs[index];
	    }
	    for(ll int right = index; right<n; right+k) // And here
	    {
	        sum += inputs[index];
	    }

what are left-k and right+k doing?

To rectify TLE, make them left -= k and right += k.

Hi! I used heap to solve this,
Solution: 49411751 | CodeChef, I am getting AC, just wanted to know is this correct way to implement?

how tester solution in o(n) update query and query take o(logn) and you are running for loop also so how it is o(n) it should be o(nlogn).
please answer @cherry0697

hey guys @suman_18733097 @cubefreak777 @jayeshasawa001
i wrote the recursive code for this above problem here

https://www.codechef.com/viewsolution/49992783

how do i memoize it or make it iterative please help