oj.uz

Submission #895255

# Submission time Handle Problem Language Result Execution time Memory
895255 2023-12-29T17:01:08 Z Andrey Luxury burrow (IZhO13_burrow) C++14
100 / 100
 877 ms 18168 KB 
#include<bits/stdc++.h>
using namespace std;

int n,m;
int table[1001][1001];
int wow[1001][1001];

int solve(int col) {
    long long big = 0,a;
    vector<long long> haha(m);
    vector<long long> ans(m,1);
    for(long long i = 0; i < m; i++) {
        haha[i] = table[col][i];
    }
    stack<pair<long long,long long>> idk;
    idk.push({-1,-1});
    for(long long i = 0; i < m; i++) {
        a = haha[i];
        while(a <= idk.top().first) {
            idk.pop();
        }
        ans[i]+=i-idk.top().second-1;
        idk.push({a,i});
    }
    while(!idk.empty()) {
        idk.pop();
    }
    idk.push({-1,m});
    for(long long i = m-1; i >= 0; i--) {
        a = haha[i];
        while(a <= idk.top().first) {
            idk.pop();
        }
        ans[i]+=idk.top().second-i-1;
        idk.push({a,i});
    }
    for(long long i = 0; i < m; i++) {
        big = max(big,haha[i]*ans[i]);
    }
    return big;
}

int calc(int a) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(wow[i][j] >= a) {
                table[i][j] = 1;
            }
            else {
                table[i][j] = 0;
            }
        }
    }
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(table[i][j] == 1) {
                table[i][j] = table[i-1][j]+1;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        ans = max(ans,solve(i));
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int k;
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> wow[i][j];
        }
    }
    int l = 0,r = 1e9;
    while(l < r) {
        int mid = (l+r+1)/2;
        if(calc(mid) >= k) {
            l = mid;
        }
        else {
            r = mid-1;
        }
    }
    cout << l << " " << calc(l);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2492 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 11 ms 6836 KB Output is correct
9 Correct 17 ms 6748 KB Output is correct
10 Correct 40 ms 7112 KB Output is correct
11 Correct 64 ms 7260 KB Output is correct
12 Correct 44 ms 6748 KB Output is correct
13 Correct 51 ms 7224 KB Output is correct
14 Correct 135 ms 7260 KB Output is correct
15 Correct 137 ms 7260 KB Output is correct
16 Correct 137 ms 7772 KB Output is correct
17 Correct 202 ms 7308 KB Output is correct
18 Correct 316 ms 9568 KB Output is correct
19 Correct 419 ms 8956 KB Output is correct
20 Correct 613 ms 13072 KB Output is correct
21 Correct 722 ms 14180 KB Output is correct
22 Correct 870 ms 18168 KB Output is correct
23 Correct 877 ms 17936 KB Output is correct
24 Correct 643 ms 10964 KB Output is correct
25 Correct 819 ms 11344 KB Output is correct