Ideone.com

download

copy

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
 
#define sz(X) ((int)X.size())
#define FOR(i,x,y) for(int i=x; i<y; ++i)
 
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
    fstream cin ("input.txt");
#endif
 
    int T; cin>>T;
    cin.ignore();
    cin.ignore();
 
    FOR(t,0,T)
    {
        if(t)
            cout<<endl;
 
        vector<int> V;
        string ch;
        int a;
 
        while (getline(cin, ch) && ch.length() > 0)
        {
            a = atoi(ch.c_str());
            V.push_back(a);
        }
 
        //LIS algorithm
        int longest, N = sz(V), end;
 
        if(N) longest = 1, end = 0; //if some values are there in the input then atleast ans is 1 which is the first value
        else  longest = 0, end = -1; //if there was a blank line in the input
 
        vector<int> L(N,1), P(N,-1);
 
        FOR(i,1,N)
        FOR(j,0,i)
        {
            if(V[j] < V[i]) //don't know if required ???
            {
                if(L[i] < L[j] + 1)
                {
                    L[i] = L[j] + 1;
                    P[i] = j; //previous index
                    longest = max(longest, L[i]);
                    end = i;
                }
            }
        }
 
        printf("Max hits: %d\n", longest);
 
        //print the values
        int e = end;
        stack<int> S;
        while (e != -1)
        {
            S.push(V[e]); e = P[e];
        }
 
        while (!S.empty())
        {
            cout<<S.top()<<endl; S.pop();
        }
    }
    return 0;
}

I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGRlcXVlPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZSA8bnVtZXJpYz4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxmc3RyZWFtPgoKI2RlZmluZSBzeihYKSAoKGludClYLnNpemUoKSkKI2RlZmluZSBGT1IoaSx4LHkpIGZvcihpbnQgaT14OyBpPHk7ICsraSkKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBtYWluKCkKewojaWZuZGVmIE9OTElORV9KVURHRQogICAgZnN0cmVhbSBjaW4gKCJpbnB1dC50eHQiKTsKI2VuZGlmCgogICAgaW50IFQ7IGNpbj4+VDsKICAgIGNpbi5pZ25vcmUoKTsKICAgIGNpbi5pZ25vcmUoKTsKCiAgICBGT1IodCwwLFQpCiAgICB7CiAgICAgICAgaWYodCkKICAgICAgICAgICAgY291dDw8ZW5kbDsKCiAgICAgICAgdmVjdG9yPGludD4gVjsKICAgICAgICBzdHJpbmcgY2g7CiAgICAgICAgaW50IGE7CgogICAgICAgIHdoaWxlIChnZXRsaW5lKGNpbiwgY2gpICYmIGNoLmxlbmd0aCgpID4gMCkKICAgICAgICB7CiAgICAgICAgICAgIGEgPSBhdG9pKGNoLmNfc3RyKCkpOwogICAgICAgICAgICBWLnB1c2hfYmFjayhhKTsKICAgICAgICB9CgogICAgICAgIC8vTElTIGFsZ29yaXRobQogICAgICAgIGludCBsb25nZXN0LCBOID0gc3ooViksIGVuZDsKCiAgICAgICAgaWYoTikgbG9uZ2VzdCA9IDEsIGVuZCA9IDA7IC8vaWYgc29tZSB2YWx1ZXMgYXJlIHRoZXJlIGluIHRoZSBpbnB1dCB0aGVuIGF0bGVhc3QgYW5zIGlzIDEgd2hpY2ggaXMgdGhlIGZpcnN0IHZhbHVlCiAgICAgICAgZWxzZSAgbG9uZ2VzdCA9IDAsIGVuZCA9IC0xOyAvL2lmIHRoZXJlIHdhcyBhIGJsYW5rIGxpbmUgaW4gdGhlIGlucHV0CgogICAgICAgIHZlY3RvcjxpbnQ+IEwoTiwxKSwgUChOLC0xKTsKCiAgICAgICAgRk9SKGksMSxOKQogICAgICAgIEZPUihqLDAsaSkKICAgICAgICB7CiAgICAgICAgICAgIGlmKFZbal0gPCBWW2ldKSAvL2Rvbid0IGtub3cgaWYgcmVxdWlyZWQgPz8/CiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKExbaV0gPCBMW2pdICsgMSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBMW2ldID0gTFtqXSArIDE7CiAgICAgICAgICAgICAgICAgICAgUFtpXSA9IGo7IC8vcHJldmlvdXMgaW5kZXgKICAgICAgICAgICAgICAgICAgICBsb25nZXN0ID0gbWF4KGxvbmdlc3QsIExbaV0pOwogICAgICAgICAgICAgICAgICAgIGVuZCA9IGk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHByaW50ZigiTWF4IGhpdHM6ICVkXG4iLCBsb25nZXN0KTsKCiAgICAgICAgLy9wcmludCB0aGUgdmFsdWVzCiAgICAgICAgaW50IGUgPSBlbmQ7CiAgICAgICAgc3RhY2s8aW50PiBTOwogICAgICAgIHdoaWxlIChlICE9IC0xKQogICAgICAgIHsKICAgICAgICAgICAgUy5wdXNoKFZbZV0pOyBlID0gUFtlXTsKICAgICAgICB9CgogICAgICAgIHdoaWxlICghUy5lbXB0eSgpKQogICAgICAgIHsKICAgICAgICAgICAgY291dDw8Uy50b3AoKTw8ZW5kbDsgUy5wb3AoKTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQ==

Success #stdin #stdout 0s 3436KB

stdin

copy

stdout

copy

Max hits: 21
33
43
84
107
113
164
288
317
380
420
445
489
493
523
554
592
620
653
677

Discover > Sphere Engine API

Discover > IDE Widget

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language