IMPA/p497/p497.cpp

#include <iostream>
#include <list>
#include <sstream>

using namespace std;

struct missile
{
    int altitude;
    int length;
    list<missile>::iterator next;
};

int main()
{
    int max = 0;

    list<missile> incoming;
    list<missile>::iterator longest, the_way;

    int test_cases;
    missile missile_entry;
    missile_entry.next = incoming.end();
    missile_entry.length = 1;
    string line;


    cin >> test_cases;
    cin.ignore();
    cin.ignore();


    for(int t = 0; t < test_cases; t++)
    {
        incoming.clear();
        max = 0;
        longest = incoming.end();


        while(getline(cin, line))
        {
            if(line.empty())
                break;

            istringstream iss_line(line);
            iss_line >> missile_entry.altitude;
            incoming.push_back(missile_entry);
        }

        for(auto i = incoming.end(); i != incoming.begin(); i--)
        {
            prev(i)->length = 1;

            for(auto y = i; y != incoming.end(); y++)
            {
                if((y->altitude > prev(i)->altitude) && ((y->length) >= prev(i)->length))
                {
                    prev(i)->length = y->length + 1;
                    prev(i)->next = y;
                }
            }

            if(prev(i)->length > max)
            {
                max = prev(i)->length;
                longest = prev(i);
            }
        }

        cout << "Max hits: " << max << endl;
        the_way = longest;
        while(the_way != incoming.end())
        {
            cout << the_way->altitude << endl;
            the_way = the_way->next;
        }

        if(t != test_cases-1)
            cout << endl;
    }

    return 0;
}