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↵
#de[My code](http://ideone.com/IWs515)↵
↵
Problem statement :↵
↵
A tug of war is to be arranged at the local offince 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 ;picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.↵
}↵
↵
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;↵
}↵
Input↵
=====↵
Input starts with an integer T (≤ 100), denoting the number of test cases.↵
↵
The first line of each case is a blank line. The next line of input contains an integer n (2 ≤ n ≤ 100), the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 100000. The summation of all the weights of the people in a case will not exceed 100000.↵
↵
Output↵
======↵
For each case, print the case number and the total number weights of the people in two teams. If the weights differ, print the smaller weight first.↵
↵
Sample Input↵
↵
2↵
↵
3↵
100 90 200↵
↵
4↵
10 15 17 20↵
↵
Output for Sample Input↵
↵
Case 1: 190 200↵
Case 2: 30 32
↵
So my question is how to prevent this ?? ↵
↵
↵
#include <bits/stdc++.h>↵
#define pb push_back↵
#de
↵
Problem statement :↵
↵
A tug of war is to be arranged at the local offi
#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;↵
}↵
=====↵
Input starts with an integer T (≤ 100), denoting the number of test cases.↵
↵
The first line of each case is a blank line. The next line of input contains an integer n (2 ≤ n ≤ 100), the number of people at the picnic. n lines follow. The first line gives the weight of person 1; the second the weight of person 2; and so on. Each weight is an integer between 1 and 100000. The summation of all the weights of the people in a case will not exceed 100000.↵
↵
Output↵
======↵
For each case, print the case number and the total number weights of the people in two teams. If the weights differ, print the smaller weight first.↵
↵
Sample Input↵
↵
2↵
↵
3↵
100 90 200↵
↵
4↵
10 15 17 20↵
↵
Output for Sample Input↵
↵
Case 1: 190 200↵
Case 2: 30 32
