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 |