oj.uz

Submission #42302

# Submission time Handle Problem Language Result Execution time Memory
42302 2018-02-25T17:24:24 Z wilwxk Luxury burrow (IZhO13_burrow) C++14
0 / 100
 1 ms 376 KB 
#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; maior=1e9+4;
    for(int i=maior; i>=1; i/=2) {
        while(testa(respf+i)!=-1) respf+=i;
    }

    printf("%d %d\n", respf, testa(respf));


}

Compilation message

burrow.cpp: In function 'int main()':
burrow.cpp:41: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:44: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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Incorrect 1 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -