oj.uz

Submission #75973

# Submission time Handle Problem Language Result Execution time Memory
75973 2018-09-11T17:53:14 Z Vardanyan Luxury burrow (IZhO13_burrow) C++14
0 / 100
 2000 ms 66560 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
//int t[N][4*N];
int b[N][N];
int a[N][N];
/*
void build(int row,int v,int l,int r){
    if(l == r){
        t[row][v] = a[row][l];
        return;
    }
    int m = (l+r)/2;
    build(row,v*2,l,m);
    build(row,v*2+1,m+1,r);
    t[row][v] = min(t[row][v*2],t[row][v*2+1]);
}
int query(int row,int v,int s,int e,int l,int r){
    if(l>r) return 1000*1000*1000+5;
    if(s == l && e == r) return t[row][v];
    int m = (s+e)/2;
    return min(query(row,v*2,s,m,l,min(m,r)),query(row,v*2+1,m+1,e,max(l,m+1),r));
}*/
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++){
        for(int j = 1;j<=m;j++){
            int u = a[i][j];
            int l = j,r = j;
            while(a[i][r+1]>=u && r<m) r++;
            while(a[i][l-1]>=u && l>1) l--;
            u*=(r-l+1);
            mxs = max(mxs,u);
        }
    }
    return mxs;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    vector<int> all;
    map<int,int> mp;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
                scanf("%d",&b[i][j]);
              if(!mp[b[i][j]]){  all.push_back(b[i][j]);
                mp[b[i][j]] = 1;
                }
        }
    }
    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 main()':
burrow.cpp:46: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:51: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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 4 ms 788 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 3 ms 788 KB Output is correct
8 Correct 8 ms 1312 KB Output is correct
9 Correct 15 ms 2096 KB Output is correct
10 Correct 158 ms 4072 KB Output is correct
11 Correct 108 ms 5676 KB Output is correct
12 Correct 28 ms 5676 KB Output is correct
13 Correct 406 ms 5676 KB Output is correct
14 Correct 140 ms 5676 KB Output is correct
15 Correct 153 ms 5676 KB Output is correct
16 Correct 316 ms 14416 KB Output is correct
17 Correct 500 ms 14416 KB Output is correct
18 Correct 915 ms 29836 KB Output is correct
19 Correct 649 ms 29836 KB Output is correct
20 Correct 1989 ms 53132 KB Output is correct
21 Execution timed out 2072 ms 66560 KB Time limit exceeded
22 Halted 0 ms 0 KB -