What Goes Up - UVa 481 TLE

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

vector<int> a;
int dp[100010];
int n;
stack<int> s;

int main() {
    int tmp;
    while (scanf("%d", &tmp)!=EOF) {
        a.push_back(tmp);
    }
    n=(int)a.size();

    for (int i=0; i<n; i++) {
        dp[i]=1;

        for (int j=0; j<i; j++)
            if (a[i]>a[j])
                dp[i]=max(dp[i],dp[j]+1);
    }

    int mIdx=0;
    for (int i=0; i<n; i++)
        if (dp[i]>dp[mIdx]) mIdx=i;

    int prev=mIdx;
    s.push(a[mIdx]);

    for (int i=prev-1; i>=0; i--)
        if (a[prev]>a[i] && dp[prev]==dp[i]+1) {
            s.push(a[i]);
            prev=i;
        }

    printf("%d\n-\n", dp[mIdx]);

    while (!s.empty()) {
        printf("%d\n", s.top());
        s.pop();
    }
    return 0;
}