UVA 10131- Is Bigger Smarter?

W[a[1]] < W[a[2]] < ... < W[a[n]]
S[a[1]] > S[a[2]] > ... > S[a[n]]


Now find the LCS which maintains the rules?


Sample Input:
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900 

Sample Output:
4
4
5
9
7

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

#define M 10001
struct node
{
    int W;
    int IQ;
    int id;
} ar[M];
bool comp(node a,node b)
{
    if(a.W != b.W)
        return a.W < b.W;
    return a.IQ > b.IQ;
}
int main()
{
    int n=0,L[M],ans[M],LIS;
     while(scanf("%d %d",&ar[n].W,&ar[n].IQ)==2)
    {
        ar[n].id=n+1;
        n++;
    }
    if(n==0)
        return 0;
    sort(ar,ar+n,comp);
    for(int i=0;i<n;i++)
        L[i]=1;
    for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
            if(ar[j].W<ar[i].W&&ar[j].IQ>ar[i].IQ)
                L[i] = max(L[j] + 1, L[i]);
    int pos=0;
    for(int i=0;i<n;i++)
        if(L[i]>L[pos])
            pos = i;
    LIS = L[pos];
    printf("%d\n",LIS);
    int top=L[pos] - 1;
    ans[top]=ar[pos].id;
    for(int j=pos-1;j>=0;j--)
    {
        if(L[j]==L[pos]-1&&ar[j].W <ar[pos].W&&ar[j].IQ>ar[pos].IQ)
        {
            ans[--top]=ar[j].id;
            pos = j;
        }
    }
    for(int i=0;i<LIS;i++)
        printf("%d\n",ans[i]);
    return 0;
}