TEMA
10 % Wrong Answer
Boyiddha_ preguntado 3 years ago
getting 10% WA .
#include<bits/stdc++.h>
using namespace std;
#define mx 100007
#define ll long int
ll dp[mx][2]; // dp[...][0] -> By money & dp[...][1] -> By Points
ll solve(ll arr[],ll indx,ll n,ll k,ll presTotalPoint){
if(indx==n){
return 0;
}
if(presTotalPoint<k ){
dp[indx][0]=arr[indx]+solve(arr,indx+1,n,k,presTotalPoint+1); // By money
return dp[indx][0];
}
else{
ull a,b;
if(dp[indx][1]!=-1){
b=dp[indx][1];
}
else{
b=0+solve(arr,indx+1,n,k,presTotalPoint-k); // By Points
dp[indx][1]=b;
}
if(dp[indx][0]!=-1){
a=dp[indx][0];
}
else{
a=arr[indx]+solve(arr,indx+1,n,k,presTotalPoint+1); // By money
dp[indx][0]=a;
}
return min(a,b);
}
}
int main(){
ll n,k,pi;
cin>>n>>k;
ll arr[n];
for(ll i=0;i<n;i++){
cin>>arr[i];
}
memset(dp,-1,sizeof(dp));
ll res=solve(arr,0,n,k,0);
cout<<res<<endl;
return 0;
}