Problem Link : PROBLEM LINK
So my approach to the question was using dp. Traversing a dp twice so as to get the minimum time for each element to become non-zero (twice as to cover for circular wrapping). I don’t understand what i am doing wrong.
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9+7;
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
//freopen("Error.txt", "w", stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
cin >> t;
while(t--){
ll n, k;
cin >> n >> k;
ll arr[n];
bool flag = true;
ll sum = 0;
for(ll i = 0; i < n; i++){
cin >> arr[i];
sum+=arr[i];
if(arr[i] > 0) flag = false;
}
if(flag){
cout << 0 << endl;
}else{
ll dp[n];
for(ll i = 0; i < n; i++){
dp[i] = 1e12;
if(arr[i] > 0) dp[i] = 0;
}
for(ll i = 0; i < 2*n; i++){
if(dp[(i%n)] != 0){
int prev = ((i-1)%n >= 0) ? ((i-1)%n) : (((i-1)%n + n));
ll ini = dp[(i%n)];
dp[i%n] = min(dp[prev], dp[(i+1)%n])+1;
dp[(i%n)] = min(dp[(i%n)], ini);
//cout << "i " << i << " " << dp[(i%n)] << " prev " << prev << endl;
}
}
for(ll i = 0; i < n; i++){
dp[i]++;
//cout << dp[i] << " ";
}
//cout << endl;
ll maxAns = 0;
map<ll, ll> m;
for(auto x: dp){
m[x]++;
maxAns = max(maxAns, x);
}
ll ans = 0;
if(k >= maxAns){
ans += (k-maxAns)*n*2;
}
ll pos = 0;
ll time = min(maxAns, k);
for(auto x: m){
if(x.first <= time){
ans += ((pos+x.second)*2);
pos += x.second;
}
else break;
}
cout << sum + ans << endl;
}
}
}