Submission #75996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
75996	2018-09-11T18:58:46 Z	Vardanyan	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	767 ms	12640 KB

burrow

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int b[N][N];
int a[N][N];
int L[N];
int R[N];
int n,m,k;
int get(int x){
    int mxs = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(b[i][j] >= x) a[i][j] = a[i-1][j]+1;
            else a[i][j] = 0;
        }
    }
    for(int i = 1;i<=n;i++){
        memset(L,0,sizeof(L));
        memset(R,0,sizeof(R));
        for(int j = 1;j<=m;j++){
            int u = a[i][j];
            int l = j,r = j;
            L[j] = j;
            while(l>1){
                if(L[l]<l && L[l]) l = L[l];
                else l--;
                if(a[i][l]<u){
                    l++;
                    break;
                }
            }
            L[j] = l;
        }
        for(int j = m;j>=1;j--){
            int r = j;
            int u = a[i][j];
            while(r<m){
                    if(R[r]>r) r = R[r];
                    else r++;
                    if(a[i][r]<u){
                        r--;
                        break;
                    }
            }
            R[j] = r;
        }
        for(int j = 1;j<=m;j++)
        mxs = max(mxs,(R[j]-L[j]+1)*a[i][j]);
    }
    return mxs;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    vector<int> all;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
                scanf("%d",&b[i][j]);
                    all.push_back(b[i][j]);
        }
    }
    sort(all.begin(),all.end());
    int l = 0;
    int r = all.size()-1;
    int ans = 0;
    int mxs = k;
    while(l<=r){
        int m = (l+r)/2;
        int y = get(all[m]);
        if(y>=k){
            ans = m;
            mxs = y;
            l = m+1;
        }
        else r = m-1;
    }
    cout<<all[ans]<<" "<<mxs<<endl;
    return 0;
}

Compilation message

burrow.cpp: In function 'int get(int)':
burrow.cpp:22:23: warning: unused variable 'r' [-Wunused-variable]
             int l = j,r = j;
                       ^
burrow.cpp: In function 'int main()':
burrow.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
burrow.cpp:57:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&b[i][j]);
                 ~~~~~^~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	580 KB	Output is correct
4	Correct	2 ms	612 KB	Output is correct
5	Correct	3 ms	656 KB	Output is correct
6	Correct	3 ms	784 KB	Output is correct
7	Correct	2 ms	784 KB	Output is correct
8	Correct	8 ms	1468 KB	Output is correct
9	Correct	15 ms	2500 KB	Output is correct
10	Correct	33 ms	2500 KB	Output is correct
11	Correct	47 ms	2896 KB	Output is correct
12	Correct	35 ms	4816 KB	Output is correct
13	Correct	37 ms	4816 KB	Output is correct
14	Correct	103 ms	4816 KB	Output is correct
15	Correct	123 ms	4816 KB	Output is correct
16	Correct	111 ms	4816 KB	Output is correct
17	Correct	125 ms	5740 KB	Output is correct
18	Correct	278 ms	7016 KB	Output is correct
19	Correct	382 ms	8296 KB	Output is correct
20	Correct	581 ms	9664 KB	Output is correct
21	Correct	580 ms	11032 KB	Output is correct
22	Correct	736 ms	12640 KB	Output is correct
23	Correct	767 ms	12640 KB	Output is correct
24	Correct	615 ms	12640 KB	Output is correct
25	Correct	616 ms	12640 KB	Output is correct