Przekroczony limit czasu w zadaniu

0

https://pl.spoj.com/problems/UPS12_B/
https://ideone.com/rJoM5v

    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
     
    int main(){
     
    	ios_base::sync_with_stdio(false);
     
    	int n;
     
    	cin >> n;
     
    	int w[n];
    	int h[n];
     
    	for(int i=0; i<n; i++)
    		cin>>w[i];
    	for(int i=0; i<n; i++)
    		cin >>h[i];
     
    	int suma;
    	vector<int>wynik;
     
    	for(int i=0; i<n-2; i++)
    		for(int j=i+1; j<n-1; j++)
    			for(int k=j+1; k<n; k++)
    				if(w[i]<w[j] && w[j]<w[k])
    				{
    					suma=w[i]+w[j]+w[k];
    					wynik.push_back(suma);
    				}
     
    	sort(wynik.begin(),wynik.end());
     
    	if(wynik.size())
    		cout << wynik[wynik.size()-1]<<"\n";
    	else
    		cout<<wynik.size()<<"\n";		
     
    }

W jaki sposób to przyspieszyć? Pisząc to miałem w głowie problem plecakowy lecz później najdłuższy podciąg ale koniec końców wyszło to brzydactwo :P

1
 sort(wynik.begin(),wynik.end());

        if(wynik.size())
            cout << wynik[wynik.size()-1]<<"\n";
        else
            cout<<wynik.size()<<"\n";     

Trochę dużo zachodu aby znaleźć wartość maksymalną. Możesz w pętli uaktualniać sobie tę wartość a nie wpisywać wszystkie do wektora.
Zabrakło też warunków na wysokość beczek.

0
  1. Zapomniałeś o warunku h[i]<h[j]<h[k]
  2. Warunek w[i]<w[j] można sprawdzić przed pętlą po k (h[i]<h[j] również)
  3. Nie potrzebujesz magazynować wszystkie poprawne trójki best_sum=max(best_sum,w[i]+w[j]+w[k])
3

twój kod ma złożoność obliczeniową O(n^3) to jest po prostu za dużo. Twoje rozwiązanie kwalifikuje się na określenie "brutal force".
Musisz wymyślić sprawniejszą metodę odnalezienia wyniku.

1 użytkowników online, w tym zalogowanych: 0, gości: 1