TEMA

10 % Wrong Answer

Boyiddha_ preguntado 4 months 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;
}

Recuerda no enviar soluciones. Tu mensaje puede ser revisado por nuestros moderadores.

  • feodorv respondido 4 months ago

    I did not undertand your DP, sorry. You can try to solve the problem greedily.