[IOI 2005 Day 1] Garden(정원) ★

문제 링크

예전 IOI라서 서브태스크가 없다.

플1... 까지는 아닌 것 같다.

풀이

겹치지 않는 두 직사각형을 선택한다는 조건을 잘 고민해보면,

수직선 하나를 두고 양쪽에서 선택한다는 의미가 된다.

 

그래서 아래의 색칠된 직사각형이 좌상단 영역에서 둘레가 최소가 되는 조건 만족 직사각형이라면,

저기 여러가지 나머지 직사각형들 중 최소가 되는 것과 함께 고려해주면 된다는 것을 알 수 있다.

따라서, $a(i,j):=(i,j)$를 우하단 점으로 하는 직사각형들 중 최소,

$b(i,j)=i\le i',\, j\le j'$일 때, $(i',j')$을 좌상단 점으로 하는 직사각형들 중 최소로 잡고

$\min$ 2D 누적합을 진행해주면 된다.

 

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
void o_o(){ cerr << endl; }
template <class H, class...T> void o_o(H h,T...t) { cerr << ' ' << h; o_o(t...); }
#define debug(...) cerr<<'['<<#__VA_ARGS__<<"]:",o_o(__VA_ARGS__)
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define size(x) int((x).size())
#define fi first
#define se second

#define per(i,a,b) for (auto i = (b); i >= (a); --i)

const int L = 253, W = 253;
int l, w, n, k;
int c[L][W], p[L][W];
int a[L][W], b[L][W];

inline int s(int x1, int y1, int x2, int y2) {
    return p[x2][y2]-p[x1-1][y2]-p[x2][y1-1]+p[x1-1][y1-1];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> l >> w >> n >> k;
    rep(i,1,n) {
        int x, y;
        cin >> x >> y;
        c[x][y]++;
    }
    rep(i,1,l) rep(j,1,w) p[i][j] = p[i-1][j]+p[i][j-1]-p[i-1][j-1]+c[i][j];
    fill(a[0],a[L],1e9);
    rep(i,1,l) rep(j,1,w) {
        int y = i;
        rep(x,1,j) {
            while (y >= 1 and s(y,x,i,j) < k) y--;
            if (y >= 1 and s(y,x,i,j) >= k) {
                a[i][j] = min(a[i][j], i-y+1 + j-x+1);
            }
        }
    }
    fill(b[0],b[L],1e9);
    per(i,1,l) per(j,1,w) {
        int y = i;
        per(x,j,w) {
            while (y <= l and s(i,j,y,x) < k) y++;
            if (y <= l and s(i,j,y,x) >= k) {
                b[i][j] = min(b[i][j], y-i+1 + x-j+1);
            }
        }
        b[i][j] = min({b[i][j],b[i+1][j],b[i][j+1]});
    }
    int answer = 1e9;
    rep(i,1,l) rep(j,1,w) {
        answer = min({answer, a[i][j] + b[1][j+1], a[i][j] + b[i+1][1]});
    }
    if (answer == 1e9) cout << "NO";
    else cout << 2*answer;
}