I am getting WA for CHRL4 problem. I have implemented an idea suggested in the editorial for the problem that should work for subtask1 but should time out for subtask2. Even that is not happening. I am just getting WA for all test cases.
Here is the link to the problem:
Here is the code:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<set>
#include<vector>
#include<utility>
#define MOD 1000000007
using namespace std;
int main ( ) {
long long n, k, minipos, cost[100006], ans[100006];
double mini, mi[100006];
cin>>n>>k;
for ( int i = 0; i < n; i++ ) {
scanf("%lld", &cost[i]);
}
mi[0] = log(cost[0]);
ans[0] = cost[0];
for ( int i = 1; i < n; i++ ) {
mini = -1;
for ( int j = 1; ( ( j <= k ) && ( ( i - j ) >= 0 ) ); j++ ) {
if( mini == -1 ) {
mini = mi[i-j];
minipos = i - j;
}
else if ( mini > mi[i-j] ) {
mini = mi[i-j];
minipos = i - j;
}
}
mi[i] = mini + log(cost[i]);
ans[i] = ( ( cost[minipos] % MOD ) * ( cost[i] % MOD ) ) % MOD;
}
cout<<ans[n-1];
return 0;
}