# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
42300 | wilwxk | Luxury burrow (IZhO13_burrow) | C++14 | 2 ms | 488 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e3+3;
int ori[MAXN][MAXN];
int h[MAXN][MAXN];
int ent[MAXN];
stack<int> st, sti;
int xx, yy, x, respf, maior;
int testa(int k) {
for(int i=1; i<=xx; i++) {
for(int j=1; j<=yy; j++) {
if(ori[i][j]>=k) h[i][j]=1; else h[i][j]=0;
if(h[i][j]==1) h[i][j]=h[i-1][j]+1; else h[i][j]=0;
}
}
int resp=0;
while(st.size()) { st.pop(); sti.pop(); } ent[0]=0;
st.push(-2); sti.push(0);
for(int i=1; i<=xx; i++) {
for(int j=1; j<=yy+1; j++) {
int cur=h[i][j]; if(j==yy+1) cur=-1;
while(st.top()>=cur) {
int area=st.top()*(j-ent[sti.top()]);
resp=max(resp, area);
st.pop(); sti.pop();
}
ent[j]=sti.top(); ent[j]++;
st.push(h[i][j]); sti.push(j);
}
}
//printf("%d : %d\n", k, resp);
if(resp>=x) return resp;
else return -1;
}
int main() {
scanf("%d %d %d", &xx, &yy, &x);
for(int i=1; i<=xx; i++) {
for(int j=1; j<=yy; j++) {
scanf("%d", &ori[i][j]); maior=max(maior, ori[i][j]);
}
}
respf=0;
for(int i=maior; i>=1; i/=2) {
while(testa(respf+i)!=-1) respf+=i;
}
printf("%d %d\n", respf, testa(respf));
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |