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

10131 - Is Bigger Smarter?.cpp

#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;
}