5266 | 2023-04-24 20:09:14 | gortomi | Mágikus táblázat | cpp17 | Elfogadva 100/100 | 59ms | 10356 KiB |
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n + 2, -INT_MAX), b(m + 2, -INT_MAX);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++)
{
cin >> b[i];
b[i] *= -1;
}
stack<int> s;
s.push(0);
vector<int> l(n + 1), r(n + 1);
for(int i = 1; i <= n; i++)
{
while(a[s.top()] >= a[i]) s.pop();
l[i] = s.top();
s.push(i);
}
while(!s.empty()) s.pop();
s.push(n + 1);
for(int i = n; i >= 1; i--)
{
while(a[s.top()] >= a[i]) s.pop();
r[i] = s.top();
s.push(i);
}
vector<pair<int, int> > v(n);
for(int i = 1; i <= n; i++)
{
v[i - 1] = {a[i], r[i] - l[i] - 1};
}
sort(v.begin(), v.end());
for(int i = n - 2; i >= 0; i--)
{
v[i].second = max(v[i + 1].second, v[i].second);
}
while(!s.empty()) s.pop();
l.assign(m + 1, 0);
r.assign(m + 1, 0);
s.push(0);
for(int i = 1; i <= m; i++)
{
while(b[s.top()] >= b[i]) s.pop();
l[i] = s.top();
s.push(i);
}
while(!s.empty()) s.pop();
s.push(m + 1);
for(int i = m; i >= 1; i--)
{
while(b[s.top()] >= b[i]) s.pop();
r[i] = s.top();
s.push(i);
}
long long ans = 0;
for(int i = 1; i <= m; i++)
{
auto x = lower_bound(v.begin(), v.end(), make_pair(-b[i], 0));
if(x == v.end()) continue;
long long z = x -> second;
z *= r[i] - l[i] - 1;
ans = max(ans, z);
}
cout << ans;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1832 KiB | ||||
2 | Elfogadva | 8ms | 2488 KiB | ||||
subtask2 | 14/14 | ||||||
3 | Elfogadva | 3ms | 2380 KiB | ||||
4 | Elfogadva | 3ms | 2592 KiB | ||||
5 | Elfogadva | 3ms | 2804 KiB | ||||
6 | Elfogadva | 3ms | 2752 KiB | ||||
7 | Elfogadva | 2ms | 2836 KiB | ||||
8 | Elfogadva | 3ms | 3064 KiB | ||||
subtask3 | 27/27 | ||||||
9 | Elfogadva | 3ms | 3456 KiB | ||||
10 | Elfogadva | 3ms | 3668 KiB | ||||
11 | Elfogadva | 3ms | 3620 KiB | ||||
12 | Elfogadva | 3ms | 3780 KiB | ||||
13 | Elfogadva | 3ms | 3988 KiB | ||||
14 | Elfogadva | 3ms | 4192 KiB | ||||
15 | Elfogadva | 3ms | 4168 KiB | ||||
16 | Elfogadva | 3ms | 4172 KiB | ||||
17 | Elfogadva | 3ms | 4444 KiB | ||||
subtask4 | 21/21 | ||||||
18 | Elfogadva | 45ms | 8644 KiB | ||||
19 | Elfogadva | 45ms | 8644 KiB | ||||
20 | Elfogadva | 37ms | 8640 KiB | ||||
21 | Elfogadva | 35ms | 8640 KiB | ||||
22 | Elfogadva | 32ms | 8888 KiB | ||||
23 | Elfogadva | 35ms | 8336 KiB | ||||
24 | Elfogadva | 3ms | 4520 KiB | ||||
subtask5 | 38/38 | ||||||
25 | Elfogadva | 54ms | 8900 KiB | ||||
26 | Elfogadva | 59ms | 9160 KiB | ||||
27 | Elfogadva | 54ms | 9264 KiB | ||||
28 | Elfogadva | 54ms | 9276 KiB | ||||
29 | Elfogadva | 48ms | 9208 KiB | ||||
30 | Elfogadva | 41ms | 9500 KiB | ||||
31 | Elfogadva | 45ms | 9500 KiB | ||||
32 | Elfogadva | 35ms | 7972 KiB | ||||
33 | Elfogadva | 34ms | 7900 KiB | ||||
34 | Elfogadva | 26ms | 7900 KiB | ||||
35 | Elfogadva | 37ms | 7856 KiB | ||||
36 | Elfogadva | 52ms | 9420 KiB | ||||
37 | Elfogadva | 50ms | 10332 KiB | ||||
38 | Elfogadva | 50ms | 10356 KiB | ||||
39 | Elfogadva | 50ms | 9592 KiB | ||||
40 | Elfogadva | 48ms | 10060 KiB | ||||
41 | Elfogadva | 43ms | 8988 KiB | ||||
42 | Elfogadva | 39ms | 9420 KiB | ||||
43 | Elfogadva | 41ms | 10060 KiB | ||||
44 | Elfogadva | 43ms | 9564 KiB |