oj.uz

Submission #378463

# Submission time Handle Problem Language Result Execution time Memory
378463 2021-03-16T21:40:59 Z ijxjdjd Luxury burrow (IZhO13_burrow) C++14
100 / 100
 545 ms 15108 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = 1000;

bool active[MAXN][MAXN];
int board[MAXN][MAXN];
int histoArea(vector<int>& hist) {
    stack<pair<int, int>> st;
    int mx = 0;
    FR(i, hist.size()) {
        while (st.size() && hist[st.top().first] >= hist[i]) {
            mx = max(hist[st.top().first] * (i-st.top().second-1), mx);
            st.pop();
        }
        st.push({i, (st.size() ? st.top().first : -1)});
    }
    return mx;
}
int maxArea(int N, int M) {
    vector<int> cur(M+1);
    cur[M] = -1;
    int res = 0;
    FR(i, N) {
        FR(j, M) {
            if (active[i][j]) {
                cur[j]++;
            }
            else {
                cur[j] = 0;
            }
        }
        res = max(res, histoArea(cur));
    }
    return res;
}
int findUp(int N, int M, int b) {
    memset(active, 0, sizeof(active));
    FR(i, N) {
        FR(j, M) {
            if (board[i][j] >= b) {
                active[i][j] = true;
            }
        }
    }
    return maxArea(N, M);

}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, M, K;
	cin >> N >> M >> K;
	FR(i, N) {
        FR(j, M) {
            cin >> board[i][j];
        }
	}
	int low = 0;
	int high = (int)(1e9) + 5;
	int cnt = 0;
	while (low < high) {
        int mid = (low + high+1)/2;
        int res = findUp(N, M, mid);
        if (res >= K) {
            low = mid;
            cnt = res;
        }
        else {
            high = mid-1;
        }
	}
	cout << low << " " << findUp(N, M, low) << '\n';
	return 0;
}

Compilation message

burrow.cpp: In function 'int main()':
burrow.cpp:66:6: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
   66 |  int cnt = 0;
      |      ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1388 KB Output is correct
2 Correct 2 ms 1388 KB Output is correct
3 Correct 2 ms 1388 KB Output is correct
4 Correct 3 ms 1388 KB Output is correct
5 Correct 3 ms 1388 KB Output is correct
6 Correct 3 ms 1516 KB Output is correct
7 Correct 3 ms 1388 KB Output is correct
8 Correct 8 ms 1772 KB Output is correct
9 Correct 12 ms 2284 KB Output is correct
10 Correct 34 ms 2540 KB Output is correct
11 Correct 47 ms 2924 KB Output is correct
12 Correct 29 ms 3436 KB Output is correct
13 Correct 37 ms 2156 KB Output is correct
14 Correct 81 ms 3436 KB Output is correct
15 Correct 82 ms 3456 KB Output is correct
16 Correct 99 ms 4204 KB Output is correct
17 Correct 110 ms 3876 KB Output is correct
18 Correct 222 ms 6636 KB Output is correct
19 Correct 247 ms 5996 KB Output is correct
20 Correct 421 ms 10092 KB Output is correct
21 Correct 428 ms 11136 KB Output is correct
22 Correct 537 ms 15108 KB Output is correct
23 Correct 545 ms 15084 KB Output is correct
24 Correct 384 ms 8044 KB Output is correct
25 Correct 461 ms 8192 KB Output is correct