Solution to Largest (Zero Carbon) Footprint (http://wcipeg.com/problem/ccc11s2p6)

gistfile1.txt

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int X[10010];
int Y[10010];
vector<int> XS[10010];
vector<short> UP[10010];
int DOWN[10010];
int GAPSET[10010];

bool cmpbyy(int i, int j) { return Y[i] > Y[j]; }

int main() {
  int N, M, T;
  cin >> N >> M >> T;
  for(int i = 0; i < T; i++) {
    cin >> X[i] >> Y[i];
    XS[X[i]].push_back(i);
  }
  for(int i = 0; i <= N; i++) sort(XS[i].begin(), XS[i].end(), cmpbyy);
  for(int i = 0; i < T; i++) {
    UP[i].push_back(0);
    for(int x = X[i] - 1; x >= 0; x--) {
      int xhi = UP[i].back();
      for(int j = 0; j < XS[x].size(); j++) {
        int k = XS[x][j];
        if(Y[k] < Y[i]) xhi = max(xhi, Y[k]);
      }
      UP[i].push_back(xhi);
    }
    reverse(UP[i].begin(), UP[i].end());
  }

  int result = 0;
  for(int xlo = 0; xlo < N; xlo++) {
    int gap = M;
    memset(GAPSET, 0, sizeof(GAPSET));
    memset(DOWN, -1, sizeof(DOWN));
    GAPSET[gap] = 1;
    DOWN[0] = M;
    for(int xhi = xlo + 1; xhi <= N; xhi++) {
      result = max(result, (xhi - xlo) * gap);
      for(int i = 0; i < XS[xhi].size(); i++) {
        int j = XS[xhi][i];
        int y = Y[j];
        int upy = UP[j][xlo + 1];
        if(DOWN[y] != -1) continue;
        int downy = DOWN[upy];
        DOWN[upy] = y;
        DOWN[y] = downy;
        GAPSET[downy - upy]--;
        GAPSET[y - upy]++;
        GAPSET[downy - y]++;
      }
      for(; GAPSET[gap] == 0; gap--);
    }
  }
  cout << result << endl;
}