# IOI 2005, Garden

Hi there,
I was solving IOI 2005, Garden problem, but when I submitted I got only partially correct. I checked my code with different test cases, and it always worked.

Here is my code:

#include <bits/stdc++.h>
using namespace std;

#define INF 100000

int slidingWindow(vector<vector<int>>& l, int n, int m, int k){
int st = -1,en = -1,perimeter = INF;
vector<vector<int>> prefixL(n+1,vector<int>(m+1));
vector<int> rowSt(n, INF), rowEn(n, INF), colSt(m, INF), colEn(m, INF);
for(int i=0;i<=n;i++)   prefixL[i][0] = 0;
for(int j=0;j<=m;j++)   prefixL[0][j] = 0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
prefixL[i][j] = (l[i-1][j-1] + prefixL[i-1][j] + prefixL[i][j-1] - prefixL[i-1][j-1]);
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
st = 0;en = 0;
int cnt = prefixL[j+1][1] - prefixL[j+1][0] - prefixL[i][1] + prefixL[i][0];
for(;k<m;){
if(cnt > k){
if(st == en){   st++;en++;}
else            st++;
}else if(cnt < k){
en++;
}else{
while(st < en && (prefixL[j+1][st+1] - prefixL[j+1][st] - prefixL[i][st+1] + prefixL[i][st] == 0))
st++;
perimeter = 2*((j-i+1)+(en-st+1));
rowSt[j] = min(rowSt[j], perimeter);
rowEn[i] = min(rowEn[i], perimeter);
colSt[en] = min(colSt[en], perimeter);
colEn[st] = min(colEn[st], perimeter);
en++;
}
if(en == m) break;
cnt = prefixL[j+1][en+1] - prefixL[j+1][st] - prefixL[i][en+1] + prefixL[i][st];
}
}
}
int ans = INF;
for(int i=1;i<n;i++)
ans = min(ans, rowSt[i-1] + rowEn[i]);
for(int j=1;j<m;j++)
ans = min(ans, colSt[j-1] + colEn[j]);
return ans;
}

int main() {
int l,w,n,k;
cin >> l >> w
>> n >> k;
vector<vector<int>> roseGarden(l,vector<int>(w, 0));
int x,y;
while(n--){
cin >> x >> y;
x--;y--;
roseGarden[x][y]++;
}
int ans = slidingWindow(roseGarden,l,w,k);
if(ans == INF)  cout << "NO\n";
else            cout << ans;
return 0;
}