IOI 2005, Garden

Problems and Contests
#1

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.

Question link : Garden

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;
}

Please help me, if you have a small test case where my program fails, then please share that.

Thanks.

#2

Garden cleaning services encompass a range of tasks aimed at maintaining and enhancing the aesthetic appeal and functionality of outdoor spaces. garden cleaning service These services typically include pruning, trimming, and shaping of plants, as well as removal of weeds, leaves, and debris. Professional garden cleaners also undertake lawn mowing, edging, and hedge trimming to ensure a neat and well-manicured appearance. Beyond aesthetics, garden cleaning services contribute to the health of plants by promoting proper growth and reducing disease risk. They may also include soil cultivation, mulching, and fertilization to improve soil quality and plant vitality. Overall, these services are essential for homeowners who wish to keep their gardens beautiful, healthy, and enjoyable throughout the seasons without the hassle of manual labor or specialized equipment.