52662023-04-24 20:09:14gortomiMágikus táblázatcpp17Elfogadva 100/10059ms10356 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1832 KiB
2Elfogadva8ms2488 KiB
subtask214/14
3Elfogadva3ms2380 KiB
4Elfogadva3ms2592 KiB
5Elfogadva3ms2804 KiB
6Elfogadva3ms2752 KiB
7Elfogadva2ms2836 KiB
8Elfogadva3ms3064 KiB
subtask327/27
9Elfogadva3ms3456 KiB
10Elfogadva3ms3668 KiB
11Elfogadva3ms3620 KiB
12Elfogadva3ms3780 KiB
13Elfogadva3ms3988 KiB
14Elfogadva3ms4192 KiB
15Elfogadva3ms4168 KiB
16Elfogadva3ms4172 KiB
17Elfogadva3ms4444 KiB
subtask421/21
18Elfogadva45ms8644 KiB
19Elfogadva45ms8644 KiB
20Elfogadva37ms8640 KiB
21Elfogadva35ms8640 KiB
22Elfogadva32ms8888 KiB
23Elfogadva35ms8336 KiB
24Elfogadva3ms4520 KiB
subtask538/38
25Elfogadva54ms8900 KiB
26Elfogadva59ms9160 KiB
27Elfogadva54ms9264 KiB
28Elfogadva54ms9276 KiB
29Elfogadva48ms9208 KiB
30Elfogadva41ms9500 KiB
31Elfogadva45ms9500 KiB
32Elfogadva35ms7972 KiB
33Elfogadva34ms7900 KiB
34Elfogadva26ms7900 KiB
35Elfogadva37ms7856 KiB
36Elfogadva52ms9420 KiB
37Elfogadva50ms10332 KiB
38Elfogadva50ms10356 KiB
39Elfogadva50ms9592 KiB
40Elfogadva48ms10060 KiB
41Elfogadva43ms8988 KiB
42Elfogadva39ms9420 KiB
43Elfogadva41ms10060 KiB
44Elfogadva43ms9564 KiB