467C-CodeForces Time Complexity

Question

今日、私はcodeforcesの問題を解決するために何度も試みましたが、私はdpを使用しましたが、TLはまだ失敗します。私のコードのどの部分が長い時間を取るかを教えてもらえますか？ありがとう！ここに私の提出の

#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; 
    } 

リンク：http://codeforces.com/contest/467/submission/24322748

Answer 1

の答えは、このようにあなたが最初に-1にあなたの動的配列のすべての要素を設定する必要があり、その後、あなたの関数にあなたがいるかどうかを確認する必要があり、0であってもよいですそれらが-1に等しいかどうか。