mahmoud-a
8/24/2017 - 1:23 PM

## https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1072

``````#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 1e3+3;
const int OO = 1e9;

int n;
map<pair<int, int>, int> m;
pair<int, int> a[MAX];
int cache[MAX][MAX];

int maxEle(int i, int pre) {
if(i == n)
return 0;
int &ret = cache[i][pre];
if(ret != -1)
return ret;
ret = -1*OO;
int ch1 = maxEle(i+1, pre);
int ch2 = -1*OO;
if((a[i].second < a[pre].second && a[pre].first < a[i].first) || pre == 1001) {
ch2 = maxEle(i+1, i) + 1;
}
return ret = max(ch1, ch2);
}

pair<int, int> key;
void trackOperations(int i, int pre) {
if(i == n)
return;

int ch2 = -1*OO;
if((a[i].second < a[pre].second && a[pre].first < a[i].first) || pre == 1001) {
ch2 = maxEle(i+1, i) + 1;
}
int opt = maxEle(i, pre);

if(ch2 == opt) {
key = make_pair(a[i].first, a[i].second);
cout << m[key] << endl;
trackOperations(i+1, i);
} else {
trackOperations(i+1, pre);
}
}

int main() {
n = 0;
int x, y;
pair<int, int> p1;
clr(cache, -1);
while(cin>>x){
cin>>y;
p1 = make_pair(x, y);
a[n] = p1;
m[p1] = n+1;
n++;
}
sort(a, a+n);
x = maxEle(0, 1001);
cout << x << endl;
trackOperations(0, 1001);
return 0;
}
``````