Prevent MLE in DP (Top down)
Difference between en2 and en3, changed 137 character(s)
I just solved this dp [problem](http://lightoj.com/volume_showproblem.php?problem=1147) , i compared my code to an accepted code by trying random test cases , and it gives correct results , how ever it gives MLE in the onligne judge ( only 32M of memory ) ↵

So my question is how to prevent this ?? ↵

here is my code :↵

#include <bits/stdc++.h>↵
#define pb push_back↵
#define rep(i,n) for(int i = 0; i < n; i++)↵
#define ll long long↵

using namespace std;

ll n,x,tot,ans1,ans2=11111111;↵
ll memo[100005][101];↵
vector<int> v;↵
int solve(ll sum,int step,int chosen)↵
{↵
   if(chosen==n/2) if(ans2-ans1>abs(abs(tot-2*sum))) { ans2=max(tot-sum,sum);ans1=min(tot-sum,sum); }↵
   if(sum>tot||step>=n) return 0;↵

   if(memo[sum][step]!=-1) return memo[sum][step];↵

   solve(sum+v[step],step+1,chosen+1);↵
   solve(sum,step+1,chosen);↵
   return memo[sum][step] = sum ;↵
}↵

int main()↵
{↵
     int tc;↵
     cin >> tc ;↵
     rep(qq,tc)↵
     {↵
          cin >> n ;↵
          v.clear();↵
          tot=0;↵
          rep(i,n)↵
          {↵
              cin >> x ;↵
              v.pb(x);↵
              tot+=x;↵
          }↵

          memset(memo, -1, sizeof(memo));↵
          solve(0,0,0);↵
          cout << "Case " << qq+1 << ": " << ans1 << " " <<ans2 <<endl;↵
     }↵
     return 0;↵
}↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English myaw 2015-08-16 21:17:52 1460
en3 English myaw 2015-08-16 20:26:58 137
en2 English myaw 2015-08-16 20:26:03 137
en1 English myaw 2015-08-16 20:25:19 1333 Initial revision (published)