I just solved this dp problem , 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 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;
}