52652023-04-24 20:08:42gortomiRegexcpp17Futási hiba 0/1003ms5176 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
1Futási hiba3ms1924 KiB
2Futási hiba3ms2116 KiB
subtask20/9
3Futási hiba3ms2340 KiB
4Futási hiba3ms2592 KiB
5Futási hiba3ms2736 KiB
6Futási hiba3ms2852 KiB
7Futási hiba3ms2948 KiB
8Futási hiba3ms3316 KiB
subtask30/11
9Futási hiba3ms3588 KiB
10Futási hiba3ms3664 KiB
11Futási hiba3ms3796 KiB
12Futási hiba3ms4016 KiB
13Futási hiba3ms4228 KiB
14Futási hiba3ms4224 KiB
subtask40/13
15Futási hiba3ms4096 KiB
16Futási hiba3ms4252 KiB
17Futási hiba3ms4488 KiB
18Futási hiba3ms4424 KiB
19Futási hiba3ms4548 KiB
20Futási hiba3ms4608 KiB
subtask50/24
21Futási hiba3ms4596 KiB
22Futási hiba3ms4740 KiB
23Futási hiba3ms4976 KiB
24Futási hiba3ms4868 KiB
25Futási hiba3ms5008 KiB
26Futási hiba3ms4876 KiB
subtask60/43
27Futási hiba3ms4892 KiB
28Futási hiba3ms4896 KiB
29Futási hiba3ms5024 KiB
30Futási hiba3ms5064 KiB
31Futási hiba3ms5176 KiB
32Futási hiba3ms5112 KiB
33Futási hiba3ms5040 KiB
34Futási hiba3ms5056 KiB