i am a beginner.pl help me with this code.i submitted a solution.it s
giving op for all given testcases.but the judge is giving me a TLE.
code:
#include<iostream>
#include<map>
#define inf 999999999
using namespace std;
map<int,int> m2;
int func(map<int,int> &m1,int w)
{
if(m2[w]<inf)
return m2[w];
map<int,int>::iterator it;
int min=inf;
for(it=m1.begin();it!=m1.end();it++)
{
if((*it).second<=w)
{
int x=func(m1,w-(*it).second);
if(x+(*it).first < min)
min=x+(*it).first;
}
}
m2[w]=min;
return min;
}
main()
{
int t;
cin>>t;
while(t--)
{
int w1,w2;
cin>>w1>>w2;
int w=w2-w1,no,a,b;
cin>>no;
map<int,int> m1;
for(int i=0;i<no;i++)
{
cin>>a>>b;
m1.insert(pair<int,int>(a,b));
}
m2[0]=0;
for(int i=1;i<=w;i++)
m2[i]=inf;
func(m1,w);
if(m2[w]!=inf)
cout<<"The minimum amount of money in the piggy-bank is
"<<m2[w]<<".\n";
else
cout<<"This is impossible.\n";
}
}
pl say hw i can improve.
thanks in advance.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
