5265 2023. 04. 24 20:08:42 gortomi Regex cpp17 Futási hiba 0/100 3ms 5176 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 Futási hiba 3ms 1924 KiB
2 Futási hiba 3ms 2116 KiB
subtask2 0/9
3 Futási hiba 3ms 2340 KiB
4 Futási hiba 3ms 2592 KiB
5 Futási hiba 3ms 2736 KiB
6 Futási hiba 3ms 2852 KiB
7 Futási hiba 3ms 2948 KiB
8 Futási hiba 3ms 3316 KiB
subtask3 0/11
9 Futási hiba 3ms 3588 KiB
10 Futási hiba 3ms 3664 KiB
11 Futási hiba 3ms 3796 KiB
12 Futási hiba 3ms 4016 KiB
13 Futási hiba 3ms 4228 KiB
14 Futási hiba 3ms 4224 KiB
subtask4 0/13
15 Futási hiba 3ms 4096 KiB
16 Futási hiba 3ms 4252 KiB
17 Futási hiba 3ms 4488 KiB
18 Futási hiba 3ms 4424 KiB
19 Futási hiba 3ms 4548 KiB
20 Futási hiba 3ms 4608 KiB
subtask5 0/24
21 Futási hiba 3ms 4596 KiB
22 Futási hiba 3ms 4740 KiB
23 Futási hiba 3ms 4976 KiB
24 Futási hiba 3ms 4868 KiB
25 Futási hiba 3ms 5008 KiB
26 Futási hiba 3ms 4876 KiB
subtask6 0/43
27 Futási hiba 3ms 4892 KiB
28 Futási hiba 3ms 4896 KiB
29 Futási hiba 3ms 5024 KiB
30 Futási hiba 3ms 5064 KiB
31 Futási hiba 3ms 5176 KiB
32 Futási hiba 3ms 5112 KiB
33 Futási hiba 3ms 5040 KiB
34 Futási hiba 3ms 5056 KiB