oj.uz

Submission #503584

# Submission time Handle Problem Language Result Execution time Memory
503584 2022-01-08T11:12:31 Z lukameladze Luxury burrow (IZhO13_burrow) C++14
100 / 100
 602 ms 21724 KB 
# 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

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 7 ms 1548 KB Output is correct
9 Correct 13 ms 2816 KB Output is correct
10 Correct 28 ms 2892 KB Output is correct
11 Correct 43 ms 3832 KB Output is correct
12 Correct 31 ms 6356 KB Output is correct
13 Correct 36 ms 1944 KB Output is correct
14 Correct 90 ms 5620 KB Output is correct
15 Correct 93 ms 5580 KB Output is correct
16 Correct 97 ms 6124 KB Output is correct
17 Correct 131 ms 6736 KB Output is correct
18 Correct 234 ms 10176 KB Output is correct
19 Correct 278 ms 10344 KB Output is correct
20 Correct 430 ms 15316 KB Output is correct
21 Correct 474 ms 17172 KB Output is correct
22 Correct 592 ms 21668 KB Output is correct
23 Correct 602 ms 21724 KB Output is correct
24 Correct 429 ms 14404 KB Output is correct
25 Correct 537 ms 15164 KB Output is correct