#include
#include<stdio.h>
#include
#include
#include<string.h>
#include<math.h>
#include
#include
#include
using namespace std;
int main() {
long long n, k;
long long a[100002], pdt[100002];
cin>>n>>k;
for ( int i = 1 ; i <= n; i++ ) {
scanf("%lld", &a[i]);
}
long long m, j;
pdt[1] = a[1];
for ( int i = 2; i <= n; i++ ) {
m = -1;
j = 1;
while ( ( j <= k ) && ( (i-j) >= 1 ) ) {
if ( m == -1 ) {
m = pdt[i-j];
}
else if ( m > pdt[i-j] ) {
m = pdt[i-j];
}
j++;
}
pdt[i] = ( ( a[i] ) * (m ) ) % 1000000007;
}
cout<<pdt[n];
return 0;
}
The link to the question:
I agree that I may have to use log() for subtask2, but, I feel that this code should successfully solve atleast subtask1. It isn’t. I have used the same dp approach suggested in the editorial. Can you please let me know where I am going wrong? The sample test case works correctly.