52582023-04-24 12:32:09ZsofiaKeresztelyMágikus táblázatcpp14Időlimit túllépés 0/100600ms9664 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
vector<int> a, b;

bool ok(int mid){
    for (int i=1; i * i <= mid; i++){
        if (mid % i) continue;
        map<int, int> ma;
        int amax = -1e9, bmin = 1e9;
        if (i <= n && mid / i <= m){
            for (int j=0; j<i; j++){
                ma[a[j]]++;
            }
            amax = max(amax, ma.begin()->first);
            for (int j=i; j<n; j++){
                ma[a[j]]++;
                ma[a[j-i]]--;
                if (!ma[a[j-i]]) ma.erase(a[j-i]);
                amax = max(amax, ma.begin()->first);
            }
            ma.clear();
            for (int j=0; j<mid/i; j++){
                ma[b[j]]++;
            }
            bmin = min(bmin, ma.rbegin()->first);
            for (int j=mid/i; j<m; j++){
                ma[b[j]]++;
                ma[b[j-i]]--;
                if (!ma[b[j-i]]) ma.erase(b[j-i]);
                bmin = min(bmin, ma.rbegin()->first);
            }
        }
        if (amax >= bmin) return true;
        amax = -1e9;
        bmin = 1e9;
        ma.clear();
        if (mid / i <= n && i <= m){
            for (int j=0; j<mid/i; j++){
                ma[a[j]]++;
            }
            amax = max(amax, ma.begin()->first);
            for (int j=mid/i; j<n; j++){
                ma[a[j]]++;
                ma[a[j-i]]--;
                if (!ma[a[j-i]]) ma.erase(a[j-i]);
                amax = max(amax, ma.begin()->first);
            }
            ma.clear();
            for (int j=0; j<i; j++){
                ma[b[j]]++;
            }
            bmin = min(bmin, ma.rbegin()->first);
            for (int j=i; j<m; j++){
                ma[b[j]]++;
                ma[b[j-i]]--;
                if (!ma[b[j-i]]) ma.erase(b[j-i]);
                bmin = min(bmin, ma.rbegin()->first);
            }
        }
        if (amax >= bmin) return true;
    }
    return false;
}

int main()
{
    cin >> n >> m;
    a.resize(n);
    b.resize(m);
    for (int &x : a){
        cin >> x;
    }
    for (int &x : b){
        cin >> x;
    }
    int l = 0, r = n * m + 1;
    while (l + 1 < r){
        int mid = (l + r) / 2;
        if (ok(mid)){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    cout << l;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1812 KiB
2Időlimit túllépés600ms1768 KiB
subtask20/14
3Hibás válasz3ms2220 KiB
4Hibás válasz3ms2608 KiB
5Hibás válasz3ms2676 KiB
6Hibás válasz3ms2768 KiB
7Hibás válasz3ms2844 KiB
8Elfogadva3ms3036 KiB
subtask30/27
9Hibás válasz81ms3372 KiB
10Hibás válasz94ms3436 KiB
11Hibás válasz43ms3396 KiB
12Hibás válasz128ms3276 KiB
13Hibás válasz32ms3352 KiB
14Hibás válasz6ms3500 KiB
15Hibás válasz27ms3888 KiB
16Hibás válasz19ms4132 KiB
17Elfogadva35ms4048 KiB
subtask40/21
18Időlimit túllépés550ms3992 KiB
19Időlimit túllépés560ms4280 KiB
20Időlimit túllépés541ms5580 KiB
21Időlimit túllépés577ms4528 KiB
22Hibás válasz46ms5780 KiB
23Hibás válasz45ms5536 KiB
24Elfogadva14ms4460 KiB
subtask50/38
25Időlimit túllépés600ms8364 KiB
26Időlimit túllépés555ms8436 KiB
27Időlimit túllépés541ms8304 KiB
28Időlimit túllépés600ms8276 KiB
29Időlimit túllépés560ms8516 KiB
30Időlimit túllépés561ms8536 KiB
31Időlimit túllépés545ms8460 KiB
32Időlimit túllépés552ms7224 KiB
33Időlimit túllépés560ms7256 KiB
34Időlimit túllépés560ms4448 KiB
35Időlimit túllépés555ms6576 KiB
36Időlimit túllépés577ms8708 KiB
37Időlimit túllépés568ms9216 KiB
38Időlimit túllépés551ms8476 KiB
39Időlimit túllépés552ms9116 KiB
40Időlimit túllépés555ms9664 KiB
41Időlimit túllépés555ms8520 KiB
42Időlimit túllépés560ms7308 KiB
43Időlimit túllépés564ms7456 KiB
44Időlimit túllépés580ms7472 KiB