2 Test cases are failing ,not able to understand why… Any help will be nice!
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rrep(i,x,y) for(int i=x;i>=y;i–)
ll MAX =1e9+7;
//set st;
const ll MOD=1e18;
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1)
{res = res * a;
res%=MOD;
}
a = a * a;
a%=MOD;
b >>= 1;
}
return res%MOD;
}
void solve(){
ll n,k;
cin>>n>>k;
ll v[n+1];
rep(i,1,n+1) cin>>v[i];
ll ym=sqrt(k)+5;
ll dp[k+1][ym+1];
ll suf[k+1][ym+1];
rep(i,0,k+1){
rep(j,0,ym+1)
{dp[i][j]=-MOD;
suf[i][j]=-MOD;
}
}
rep(i,0,k+1){
dp[i][0]=0;
}
rep(i,0,k+1){
rrep(j,ym-1,0){
suf[i][j]=max(suf[i][j+1],dp[i][j]);
}
}
rep(i,1,n+1){
rrep(j,k,0){
rrep(l,ym,0){
if(j-l>=0 && l-1>=0)
dp[j][l]=l*v[i]+suf[j-l][l-1];
else if(j-l>=0 && l==0){
dp[j][l]=suf[j][l];
}
}
}
rrep(j,k,0){
rrep(l,ym-1,0){
suf[j][l]=max(suf[j][l+1],dp[j][l]);
}
}
}
ll ans=-MOD;
rep(j,0,k+1){
rep(i,0,ym+1){
ans=max(ans,dp[j][i]);
//cout<<dp[k][i]<<endl;
}
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t=1;
while(t){
//sol.clear();
// memset(dp,-1,sizeof(dp));
solve();
t–;
}
}