10325 2024. 03. 30 21:23:05 szil Mágikus táblázat cpp17 Elfogadva 100/100 71ms 54780 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 3520 KiB
2 Elfogadva 9ms 4668 KiB
subtask2 14/14
3 Elfogadva 3ms 4340 KiB
4 Elfogadva 3ms 4404 KiB
5 Elfogadva 3ms 4680 KiB
6 Elfogadva 3ms 4800 KiB
7 Elfogadva 3ms 4664 KiB
8 Elfogadva 3ms 4976 KiB
subtask3 27/27
9 Elfogadva 4ms 5392 KiB
10 Elfogadva 4ms 5520 KiB
11 Elfogadva 4ms 5536 KiB
12 Elfogadva 4ms 5884 KiB
13 Elfogadva 4ms 5876 KiB
14 Elfogadva 4ms 6304 KiB
15 Elfogadva 4ms 6200 KiB
16 Elfogadva 4ms 6252 KiB
17 Elfogadva 4ms 6296 KiB
subtask4 21/21
18 Elfogadva 59ms 12924 KiB
19 Elfogadva 45ms 13816 KiB
20 Elfogadva 48ms 14704 KiB
21 Elfogadva 45ms 15652 KiB
22 Elfogadva 41ms 15928 KiB
23 Elfogadva 41ms 17236 KiB
24 Elfogadva 4ms 11956 KiB
subtask5 38/38
25 Elfogadva 71ms 19724 KiB
26 Elfogadva 71ms 21760 KiB
27 Elfogadva 71ms 23816 KiB
28 Elfogadva 71ms 26016 KiB
29 Elfogadva 65ms 28040 KiB
30 Elfogadva 41ms 29960 KiB
31 Elfogadva 61ms 31792 KiB
32 Elfogadva 46ms 31700 KiB
33 Elfogadva 35ms 32968 KiB
34 Elfogadva 34ms 34260 KiB
35 Elfogadva 41ms 35292 KiB
36 Elfogadva 68ms 38792 KiB
37 Elfogadva 67ms 40864 KiB
38 Elfogadva 64ms 43152 KiB
39 Elfogadva 54ms 45344 KiB
40 Elfogadva 50ms 46780 KiB
41 Elfogadva 45ms 48180 KiB
42 Elfogadva 39ms 50720 KiB
43 Elfogadva 50ms 52548 KiB
44 Elfogadva 52ms 54780 KiB