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