Submission #503584

#	Time	Username	Problem	Language	Result	Execution time	Memory
503584		lukameladze	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	602 ms	21724 KiB

burrow

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
#define piii pair <int, pii>
using namespace std;
const int N = 1005;
int h[N][N],val;
int t,n,m,a[N][N],le,ri,mid,area,ans,he,wi,a1[N][N],ar,k;
int check(int mid) {
    //cout<<mid<<endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] >= mid) a1[i][j] = 1; else a1[i][j] = 0;
        }
    }
   
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a1[i][j])
            h[i][j] = h[i-1][j] + 1; else h[i][j] = 0;
        }
    } 
    ar = 0;
    //height, marcxn sadamde sheudzlia,
    for (int i = 1; i <= n; i++) {
        //cout<<i<<endl;
        stack < piii > st;
        for (int j = 1; j <= m+1; j++) {
            if (j == m + 1) val = 0;
            else
            val = h[i][j];
            //cout<<val<<" ";
            if (!st.size() || st.top().f < val) {
                st.push({val,{j,j}});
                ar = max(ar,val);
            } else {
                while (st.size() && st.top().f >= val) {
                    he = st.top().f;
                    wi = (j - st.top().s.f);
                    ar = max(ar,he*wi);//if (i == 3)
                    //cout<<he<<" "<<wi<<" "<<j<<endl;
                    st.pop();
                }
                if (!st.size()) st.push({val, {1,j}});
                else st.push({val,{st.top().s.s+1,j}});
            }
        }
    }
   // cout<<mid<<" "<<ar<<endl;
    if (ar >= k)
    return ar; else return 0;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for (int i = 1; i <= n; i++) {
	    for (int j = 1; j <= m; j++) {
	        cin>>a[i][j];
	    }
	}
	le = 1;
	ri = 1e9;
	while (le<=ri) {
	    mid = (le + ri) / 2;
	    if (check(mid)) {
	        ans = mid;
	        area = ar;
	        le = mid + 1;
	    } else ri = mid - 1;
	}
	cout<<ans<<" "<<area<<endl;
}

Compilation message (stderr)

burrow.cpp:55:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   55 | main() {
      | ^~~~

• Subtask 1: 100 / 100