467C-Code Forces Time Complexity

Question

Heute habe ich so oft versucht, ein Problem in Codeforces zu lösen, ich benutze dp, aber immer noch fehlschlagen TL. Können Sie darauf hinweisen, welcher Teil in meinem Code lange braucht? Vielen Dank !

#include<bits/stdc++.h> 

    typedef long long ll; 

    ll n,m,k,a[5000],result=0, memo[5000][5000], sum[5000]; 

    ll maxsum(int p,int t) 
    { 
     if (t==0) return 0; 
     if (memo[p][t]!=-1) 
      return memo[p][t]; 
     ll tp=0; 
     for (int i=p+m; i+(t-1)*m-1<n; ++i) 
      tp=std::max(tp,maxsum(i,t-1)); 
     memo[p][t]=tp+sum[p]; 
     return memo[p][t]; 
    } 

    int main() 
    { 
     std::ios::sync_with_stdio(0); 
     std::cin.tie(0); 
     std::cin>>n>>m>>k; 
     for (int i=0; i<n; ++i) 
      std::cin>>a[i]; 
     for (int i=0; i<m; ++i) 
      sum[0]+=a[i]; 
     for (int i=1; i+m-1<n; ++i) 
      sum[i]=sum[i-1]+a[i+m-1]-a[i-1]; 
     std::fill(&memo[0][0],&memo[n][k],-1); 
     for (int i=0; i+k*m-1<n; ++i) 
      result=std::max(result,maxsum(i,k)); 
     std::cout<<result; 
    } 

Link zu meiner Vorlage hier: http://codeforces.com/contest/467/submission/24322748

Answer 1

Die Antwort Null sein kann, so sollten Sie alle Elemente Ihrer dynamischen Arrays auf -1 gesetzt, am Anfang, und dann in Ihrer Funktion sollten Sie prüfen, ob ob sie gleich -1 sind.