optymalizacja

[Dumel]

zadanie SUMY ze SPOJa:
ma ktoś pomysł jak usprawnić ten algorytm? nie rozumiem dlaczego nie miesci sie w limicie czasu. moze sie myle ale na moje oko to liniowka, wiec powinna luzem byc akceptowana

kod:    

Kod: Zaznacz cały

//pl.spoj.pl
//zadanie: Sumy
#include<iostream>
#include<vector>
using namespace std;
void wyswietl_ciagi(int n, int min, int liczba);
vector<int> ciag(0);
vector< vector<int> > wynik(20);
bool checked[20];

int main()
{
        ios_base::sync_with_stdio(0);
        for(int i(0); i<20; ++i)
                checked[i]=false;

        int t;                              //liczba testów
        cin>>t;

        int* n = new int[t];
        for(int i(0); i<t; ++i)
                cin>>n[i];
        int N;
        for(int i(0); i<t; ++i)
        {
                N=n[i]-1;
                ciag.resize(0);
                if(checked[N]==false)
                {
                        wyswietl_ciagi(N+1, 1, N+1);
                        checked[N]=true;
                }
                else
                {
                        for(int j(0); j<wynik[N].size();++j)
                        {
                                if(wynik[N][j]!=-1)
                                        cout<<wynik[N][j]<<" ";
                                else
                                        cout<<endl;
                        }
                }
        }

        delete[] n;
        return(0);
}

void wyswietl_ciagi(int n, int min, int N)
{
        if(min<=int(n/2))
        {
            for(int i(min); i<=int(n/2); ++i)
            {
                ciag.push_back(i);
                if(n>i) {wyswietl_ciagi(n-i, i, N);}
            }
        }

        ios_base::sync_with_stdio(0);
        for(int i(0); i<ciag.size(); ++i){cout<<ciag[i]<<" "; wynik[N-1].push_back(ciag[i]);}
        cout<<n<<endl;
        wynik[N-1].push_back(n);
        wynik[N-1].push_back(-1);

        ciag.pop_back();
}

(tablica checked jest po to aby nie liczyc kilka razy tego samego. podejrzewalem ze jej brak byl zrodlem klopotow ale jednak jej wprowadzenie niewiele dalo)-- 8 marca 2009, 15:47 --liniowka to moze zle okreslenie. zlozonosc jest liniowa ze wzgledu na liczbe szukanych ciągow