I tried this problem and I saw that my solutions was way too slow compared to others. I want to know how I can improve time complexity.A job has been assigned to Jar Jar Binks, it goes as follows: There  are N spaceships parts, each with a weight of Wi kg. Given a weight W,  he has to show how many parts can be used in order to make a ship with  a weight of exactly W kg. He has to show all possible solutions, of  course if possible. Everybody knows Jar Jar Binks particularly because  of his clumsiness, so you have to help him. Write a program that  solves his problem!InputThere will be several cases, each beginning with two integers N, Q  (1<=N<=60, 0<=Q<=10000). Next there will be N positive integers  representing the weights of the N spaceship parts (1<=Wi<=1000). Q  lines will follow, each one with only one integer W, the total weight  of the spaceship. End of input will be denoted with N = 0 and Q = 0.  This case should not be processedOutputPrint a line with K integers per query in ascending order. They must  represent the amount of pieces that can be used to make a spaceship  with weight W. If there is no way to make a spaceship with weight W,  output a line with the string That's impossible! (quotes to clarify)#include <bits/stdc++.h> // I don't think this would have any impact on run-time , right?using namespace std;#define pb push_back #define FOR(i,a,b) for(int i=a;i<=b;++i)int a[60]; int dp[61][61][60001]; // dp[number of weights considered][no. of weights selected from earlier][if this sum is possible]int main() {    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // for speed improvement    int n,q;    while(1)    {        cin>>n>>q;        if(n==0&&q==0)break;        int sum=0;        FOR(i,1,n){cin>>a[i];sum+=a[i];}        memset(dp,0,sizeof(dp));        dp[0][0][0]=1;        // I know that a 3d array is not needed but this would affect only memory, right?        FOR(i,1,n)        {            dp[i][0][0]=1;            FOR(j,1,i)            {                FOR(k,0,sum)                {                    if(k>=a[i])                    dp[i][j][k]=dp[i-1][j-1][k-a[i]]; // typical dp. either a[i] is taken into account                    dp[i][j][k]|=dp[i-1][j][k];       // or it is not                }            }        }        while(q--)    // handling queries        {            int x;            cin>>x;            vector<int> v;   // we will store answers here            if(x>=1&&x<=sum)             {                FOR(j,1,n)                if(dp[n][j][x])v.pb(j);                if(v.empty())cout<<That's impossible!;                else for(auto it :v)cout<<it<< ;                cout<<\n;            }            else cout<<That's impossible!\n;        }    }    return 0;}
JARJAR challenge on SPOJ
c++;performance;c++11