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