uva 10131 - Is Bigger Smarter? Solution

uva 10131 - Is Bigger Smarter? Solution

#include<iostream>

#include<algorithm>

#include<vector>



using namespace std;



typedef pair<int, int> pii;

typedef pair<pii, int> piii;

vector<piii> vec;

vector<int> res;



bool piii_sort(piii p1, piii p2){

 if (p1.first.first<p2.first.first)

  return true;

 else

  return false;

}



void calculate_lis(int len){

  int *order = new int[len], *count = new int[len], i, j, last_index = 0, max = 1;

  fill(order, order + len, -1);

  fill(count, count + len, 1);

  for (i = 1; i < len; i++){

  for (j = 0; j < i; j++){

   if (vec[i].first.second<vec[j].first.second && vec[i].first.first>vec[j].first.first){

    if (count[j] + 1>count[i]){

     if (max < count[j] + 1){

      max = count[j] + 1;

      last_index = i;

     }

     count[i] = count[j] + 1;

     order[i] = j;

    }

   }

  }

  }

  res.push_back(vec[last_index].second);

  for (i = 1; i < max; i++){

  last_index = order[last_index];

  res.push_back(vec[last_index].second);

 }

}

int main(){

 int n = 1, w, s;

 piii p;

 pii p1;

 while (cin >>w>> s){

  vec.push_back(pair<pii, int>(pair<int, int>(w, s), n++));

 }

 sort(vec.begin(), vec.end(), piii_sort);

 calculate_lis(n - 1);

 cout << res.size() << endl;

 for (n = res.size() - 1; n >= 0; n--)

  cout << res[n] << endl;

 return 0;

}