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

```
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