103252024-03-30 21:23:05szilMágikus táblázatcpp17Elfogadva 100/10071ms54780 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 100'001;

int a[MAXN], b[MAXN], bef[MAXN], aft[MAXN], par[MAXN], siz[MAXN], biggest = 1;

int holvan(int u) {
	return par[u] == u ? u : par[u] = holvan(par[u]);
}

void unio(int u, int v) {
	u = holvan(u); v = holvan(v);
	if (u == v) return;
	siz[u] += siz[v];
	biggest = max(biggest, siz[u]);
	par[v] = u;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin >> n >> m;

	iota(par, par+MAXN, 0);
	fill(siz, siz+MAXN, 1);

	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) cin >> b[i];

	vector<int> indices(n);
	iota(indices.begin(), indices.end(), 1);
	sort(indices.begin(), indices.end(), [&](int i, int j){
		return a[i] < a[j];
	});

	stack<int> st;
	for (int i = 1; i <= n; i++) {
		while (!st.empty() && a[st.top()] >= a[i]) st.pop();
		bef[i] = st.empty() ? 0 : st.top();
		st.push(i);
	}
	st = stack<int>();
	for (int i = n; i >= 1; i--) {
		while (!st.empty() && a[st.top()] >= a[i]) st.pop();
		aft[i] = st.empty() ? n+1 : st.top();
		st.push(i);
	}

	int mine = *min_element(b+1, b+m+1);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	for (int i = 1; i < m; i++) {
		int w = max(b[i], b[i+1]);
		pq.push({w, i});
	}

	ll ans = 0;
	for (int i : indices) {
		if (a[i] < mine) continue;
		while (!pq.empty() && pq.top().first <= a[i]) {
			unio(pq.top().second, pq.top().second+1);
			pq.pop();
		}
		ll len = (aft[i] - bef[i] - 1);
		ans = max(ans, len * biggest);
	}

	cout << ans << "\n";

	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms3520 KiB
2Elfogadva9ms4668 KiB
subtask214/14
3Elfogadva3ms4340 KiB
4Elfogadva3ms4404 KiB
5Elfogadva3ms4680 KiB
6Elfogadva3ms4800 KiB
7Elfogadva3ms4664 KiB
8Elfogadva3ms4976 KiB
subtask327/27
9Elfogadva4ms5392 KiB
10Elfogadva4ms5520 KiB
11Elfogadva4ms5536 KiB
12Elfogadva4ms5884 KiB
13Elfogadva4ms5876 KiB
14Elfogadva4ms6304 KiB
15Elfogadva4ms6200 KiB
16Elfogadva4ms6252 KiB
17Elfogadva4ms6296 KiB
subtask421/21
18Elfogadva59ms12924 KiB
19Elfogadva45ms13816 KiB
20Elfogadva48ms14704 KiB
21Elfogadva45ms15652 KiB
22Elfogadva41ms15928 KiB
23Elfogadva41ms17236 KiB
24Elfogadva4ms11956 KiB
subtask538/38
25Elfogadva71ms19724 KiB
26Elfogadva71ms21760 KiB
27Elfogadva71ms23816 KiB
28Elfogadva71ms26016 KiB
29Elfogadva65ms28040 KiB
30Elfogadva41ms29960 KiB
31Elfogadva61ms31792 KiB
32Elfogadva46ms31700 KiB
33Elfogadva35ms32968 KiB
34Elfogadva34ms34260 KiB
35Elfogadva41ms35292 KiB
36Elfogadva68ms38792 KiB
37Elfogadva67ms40864 KiB
38Elfogadva64ms43152 KiB
39Elfogadva54ms45344 KiB
40Elfogadva50ms46780 KiB
41Elfogadva45ms48180 KiB
42Elfogadva39ms50720 KiB
43Elfogadva50ms52548 KiB
44Elfogadva52ms54780 KiB