oj.uz

Submission #90569

# Submission time Handle Problem Language Result Execution time Memory
90569 2018-12-22T12:31:38 Z popovicirobert Luxury burrow (IZhO13_burrow) C++14
100 / 100
 513 ms 54748 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = 1000;

int mat[MAXN + 1][MAXN + 1];
int up[MAXN + 1][MAXN + 1];
int stk[MAXN + 1], l[MAXN + 1], r[MAXN + 1];
int n, m, k;

inline int check(int val) {
    int ans = 0;
    int i, j;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            up[i][j] = (up[i - 1][j] + 1) * (mat[i][j] >= val);
        }
        int sz = 0;
        stk[0] = 0;
        for(j = 1; j <= m; j++) {
            while(sz > 0 && up[i][stk[sz]] >= up[i][j]) {
                sz--;
            }
            l[j] = stk[sz];
            stk[++sz] = j;
        }
        sz = 0;
        stk[0] = m + 1;
        for(j = m; j >= 1; j--) {
            while(sz > 0 && up[i][stk[sz]] >= up[i][j]) {
                sz--;
            }
            r[j] = stk[sz];
            stk[++sz] = j;
        }
        for(j = 1; j <= m; j++) {
            ans = max(ans, up[i][j] * (r[j] - l[j] - 1));
        }
    }
    return ans;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            cin >> mat[i][j];
        }
    }
    int res = 0;
    for(int step = 1 << 30; step; step >>= 1) {
        if(check(res + step) >= k) {
            res += step;
        }
    }
    cout << res << " " << check(res);
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 2 ms 704 KB Output is correct
3 Correct 2 ms 712 KB Output is correct
4 Correct 2 ms 824 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 2 ms 1152 KB Output is correct
8 Correct 7 ms 1664 KB Output is correct
9 Correct 11 ms 2608 KB Output is correct
10 Correct 23 ms 3004 KB Output is correct
11 Correct 43 ms 3972 KB Output is correct
12 Correct 27 ms 6112 KB Output is correct
13 Correct 31 ms 6112 KB Output is correct
14 Correct 71 ms 6360 KB Output is correct
15 Correct 74 ms 6908 KB Output is correct
16 Correct 78 ms 8032 KB Output is correct
17 Correct 84 ms 9212 KB Output is correct
18 Correct 205 ms 12880 KB Output is correct
19 Correct 230 ms 15448 KB Output is correct
20 Correct 452 ms 21992 KB Output is correct
21 Correct 413 ms 29180 KB Output is correct
22 Correct 502 ms 39548 KB Output is correct
23 Correct 513 ms 48932 KB Output is correct
24 Correct 361 ms 51512 KB Output is correct
25 Correct 362 ms 54748 KB Output is correct