Submission #42306

#	Time	Username	Problem	Language	Result	Execution time	Memory
42306		wilwxk	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	695 ms	54624 KiB

burrow

#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;
    for(int i=1; i<=xx; i++) {
        while(st.size()) { st.pop(); sti.pop(); } ent[0]=0; st.push(-2); sti.push(0);
        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)

burrow.cpp: In function 'int main()':
burrow.cpp:40:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &xx, &yy, &x);
                                    ^
burrow.cpp:43:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &ori[i][j]); maior=max(maior, ori[i][j]);
                                    ^

• Subtask 1: 100 / 100