| 5266 | 2023-04-24 20:09:14 | gortomi | Mágikus táblázat | cpp17 | Accepted 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;
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 3ms | 1832 KiB | ||||
| 2 | Accepted | 8ms | 2488 KiB | ||||
| subtask2 | 14/14 | ||||||
| 3 | Accepted | 3ms | 2380 KiB | ||||
| 4 | Accepted | 3ms | 2592 KiB | ||||
| 5 | Accepted | 3ms | 2804 KiB | ||||
| 6 | Accepted | 3ms | 2752 KiB | ||||
| 7 | Accepted | 2ms | 2836 KiB | ||||
| 8 | Accepted | 3ms | 3064 KiB | ||||
| subtask3 | 27/27 | ||||||
| 9 | Accepted | 3ms | 3456 KiB | ||||
| 10 | Accepted | 3ms | 3668 KiB | ||||
| 11 | Accepted | 3ms | 3620 KiB | ||||
| 12 | Accepted | 3ms | 3780 KiB | ||||
| 13 | Accepted | 3ms | 3988 KiB | ||||
| 14 | Accepted | 3ms | 4192 KiB | ||||
| 15 | Accepted | 3ms | 4168 KiB | ||||
| 16 | Accepted | 3ms | 4172 KiB | ||||
| 17 | Accepted | 3ms | 4444 KiB | ||||
| subtask4 | 21/21 | ||||||
| 18 | Accepted | 45ms | 8644 KiB | ||||
| 19 | Accepted | 45ms | 8644 KiB | ||||
| 20 | Accepted | 37ms | 8640 KiB | ||||
| 21 | Accepted | 35ms | 8640 KiB | ||||
| 22 | Accepted | 32ms | 8888 KiB | ||||
| 23 | Accepted | 35ms | 8336 KiB | ||||
| 24 | Accepted | 3ms | 4520 KiB | ||||
| subtask5 | 38/38 | ||||||
| 25 | Accepted | 54ms | 8900 KiB | ||||
| 26 | Accepted | 59ms | 9160 KiB | ||||
| 27 | Accepted | 54ms | 9264 KiB | ||||
| 28 | Accepted | 54ms | 9276 KiB | ||||
| 29 | Accepted | 48ms | 9208 KiB | ||||
| 30 | Accepted | 41ms | 9500 KiB | ||||
| 31 | Accepted | 45ms | 9500 KiB | ||||
| 32 | Accepted | 35ms | 7972 KiB | ||||
| 33 | Accepted | 34ms | 7900 KiB | ||||
| 34 | Accepted | 26ms | 7900 KiB | ||||
| 35 | Accepted | 37ms | 7856 KiB | ||||
| 36 | Accepted | 52ms | 9420 KiB | ||||
| 37 | Accepted | 50ms | 10332 KiB | ||||
| 38 | Accepted | 50ms | 10356 KiB | ||||
| 39 | Accepted | 50ms | 9592 KiB | ||||
| 40 | Accepted | 48ms | 10060 KiB | ||||
| 41 | Accepted | 43ms | 8988 KiB | ||||
| 42 | Accepted | 39ms | 9420 KiB | ||||
| 43 | Accepted | 41ms | 10060 KiB | ||||
| 44 | Accepted | 43ms | 9564 KiB | ||||