Submission #378463

#	Time	Username	Problem	Language	Result	Execution time	Memory
378463		ijxjdjd	Luxury burrow (IZhO13_burrow)	C++14	100 / 100	545 ms	15108 KiB

burrow

#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 (stderr)

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 / 100