Seletiva IOI 2013

tatu.cpp

// Ivan Carvalho
// Tatu - Seletiva IOI - OBI 2013
#include <bits/stdc++.h>
#define MP make_pair
#define MAXN 261
#define INF 1010
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
int matriz[MAXN][MAXN],acumulada[MAXN][MAXN],linear[MAXN];
int menor_antes[MAXN],menor_depois[MAXN],minimo[MAXN],maximo[MAXN];
vector<i4> validos;
int resp,n,m,A,B;
int main(){
	scanf("%d %d",&n,&m);
	scanf("%d %d",&A,&B);
	n = max(n,m);
	for(int i=0;i<=n+1;i++){
		menor_antes[i] = INF;
		menor_depois[i] = INF;
		minimo[i] = INF;
		maximo[i] = INF;
	}
	resp = INF;
	for(int i=1;i<=A;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		matriz[x][y]++;
	}
	//for(int i=1;i<=n;i++){
	//	for(int j=1;j<=n;j++){
	//		printf("%d ",matriz[i][j]);
	//	}
	//	printf("\n");
	//}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			acumulada[i][j] = matriz[i][j] + acumulada[i][j-1];
		}
	}
	for(int coluna_ini = 1;coluna_ini<=n;coluna_ini++){
		for(int coluna_fim = coluna_ini;coluna_fim<=n;coluna_fim++){
			int soma = 0;
			for(int i=1;i<=n;i++) linear[i] = acumulada[i][coluna_fim] - acumulada[i][coluna_ini-1];
			deque<ii> janela;
			for(int i=1;i<=n;i++){
				soma += linear[i];
				if(linear[i] != 0) janela.push_back(MP(i,linear[i]));
				while(soma > B){
					soma -= janela.front().second;
					janela.pop_front();
				}
				if(soma == B){
					validos.push_back(MP(MP(coluna_ini,coluna_fim),MP(janela.front().first,i)));
					soma -= janela.front().second;
					janela.pop_front();
				}
			}
		}
	}
	for(int i=0;i<validos.size();i++){
		int x1 = validos[i].first.first;
		int x2 = validos[i].first.second;
		int y1 = validos[i].second.first;
		int y2 = validos[i].second.second;
		int custo = (x2 - x1 + 1) + (y2 - y1 + 1);
		menor_depois[x1] = min(menor_depois[x1],custo);
		menor_antes[x2] = min(menor_antes[x2],custo);
		minimo[y2] = min(minimo[y2],custo);
		maximo[y1] = min(maximo[y1],custo);
	}
	for(int i=1;i<=n;i++){
		menor_antes[i] = min(menor_antes[i],menor_antes[i-1]);
	}
	for(int i = n;i>=1;i--){
		menor_depois[i] = min(menor_depois[i],menor_depois[i+1]);
	}
	for(int i=1;i<=n;i++){
		minimo[i] = min(minimo[i],minimo[i-1]);
	}
	for(int i = n;i>=1;i--){
		maximo[i] = min(maximo[i],maximo[i+1]);
	}
	for(int i=0;i<validos.size();i++){
		int x1 = validos[i].first.first;
		int x2 = validos[i].first.second;
		int y1 = validos[i].second.first;
		int y2 = validos[i].second.second;
		int custo = (x2 - x1 + 1) + (y2 - y1 + 1);
		int menorzinho = min(min(menor_antes[x1-1],menor_depois[x2+1]),min(minimo[y1-1],maximo[y2+1]));
		//printf("%d %d %d %d %d\n",x1,x2,y1,y2,2*(custo+menorzinho));
		resp = min(resp,custo+menorzinho);
	}
	if(resp == INF) printf("N\n");
	else printf("%d\n",2*resp);
	return 0;
}