You are not logged in. Please login at www.codechef.com to post your questions!

×

spoj PIGBANK TLE even though i am using DP

#include <iostream> using namespace std; //typedef long long int lint;

define INF 1000000000

int dp[10001]; int coins(int wt,int a[],int v[],int n) { if(wt<0) return INF;

if(wt==0) return 0;

if(dp[wt]!=INF) return dp[wt];

for(int i=0;i<n;i++) { int k=coins(wt-a[i],a,v,n); if(v[i]+k<dp[wt]) dp[wt]=v[i]+k; } return dp[wt];

} int main() { ios_base::sync_with_stdio(false);

int t; cin>>t; while(t--) { int e,f; cin>>e>>f; int wt=f-e; for(int i=0;i<wt+1;i++) dp[i]=INF;

  int n;
  cin>>n;
  int a[n],v[n];
  for(int i=0;i<n;i++)
  cin>>v[i]>>a[i];

  int m=coins(wt,a,v,n);

     if(m==INF)
     cout<<"This is impossible.\n";
     else
           cout<<"The minimum amount of money in the piggy-bank is "<<m<<"."<<endl;

} return 0; }

asked 04 Jan '15, 19:53

rising_phoenix's gravatar image

4★rising_phoenix
1
accept rate: 0%

edited 04 Jan '15, 20:01

Please either paste the code in the correct format or just provide the link on ideone or on codechef compiler .

(04 Jan '15, 22:20) ma5termind3★

Here is My AC solution to this problem. I have coded it very simple so that you can understand every part of it.

Have a look it might help you in figuring out your mistake .

http://ideone.com/wALGfV

link

answered 04 Jan '15, 22:18

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

thanks for the reply.I see you have used bottom-up approach .I converted my top-down approach to bottom up it got accepted.Does anyone know why?

(06 Jan '15, 18:20) rising_phoenix4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,172

question asked: 04 Jan '15, 19:53

question was seen: 1,474 times

last updated: 06 Jan '15, 18:20