IOI '05 P1 - Garden

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

using namespace std;

const int INF = 1e9;

int main() {
    int l, w, n, k;
    cin >> l >> w >> n >> k;
    vector<vector<int>> grid(1+l, vector<int>(1+w));
    for (int i = 0; i < n; ++i) {
        int a, b; cin >> a >> b;
        ++grid[a][b];
    }
    for (int i = 1; i <= l; ++i) {
        for (int j = 1; j <= w; ++j) {
            grid[i][j] += grid[i-1][j] + grid[i][j-1] - grid[i-1][j-1];
        }
    }
    auto getSum = [&grid](int left, int right, int top, int bottom) { // rectangle sum
        return grid[bottom][right] - grid[bottom][left-1] - grid[top-1][right] + grid[top-1][left-1];
    };

    vector<int> leftOf(1+w, INF), rightOf(1+w, INF), above(1+l, INF), below(1+l, INF);
    for (int left = 1; left <= w; ++left) {
        for (int right = left; right <= w; ++right) {
            for (int top = 1, bottom = 0; top <= l; ++top) { // sliding window
                while (bottom < l && getSum(left, right, top, bottom) < k) ++bottom;
                if (getSum(left, right, top, bottom) == k) {
                    int p = 2*(right-left+1 + bottom-top+1);
                    leftOf[right] = min(leftOf[right], p);
                    rightOf[left] = min(rightOf[left], p);
                    above[bottom] = min(above[bottom], p);
                    below[top] = min(below[top], p);
                }
            }
        }
    }

    int minPerimeterSum = INF;
    for (int i = 1; i < w; ++i) {
        leftOf[i] = min(leftOf[i], leftOf[i-1]);
        minPerimeterSum = min(minPerimeterSum, leftOf[i]+rightOf[i+1]);
    }
    for (int i = 1; i < l; ++i) {
        above[i] = min(above[i], above[i-1]);
        minPerimeterSum = min(minPerimeterSum, above[i]+below[i+1]);
    }
    if (minPerimeterSum >= INF) cout << "NO" << endl;
    else cout << minPerimeterSum << endl;
    return 0;
}