52562023-04-24 12:14:30ZsofiaKeresztelyMágikus táblázatcpp14Időlimit túllépés 0/100600ms52096 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;
        //a-ban a minimumot maximalizálom, b-men a maximumot minimalizálom
        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 (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és600ms2484 KiB
subtask20/14
3Hibás válasz3ms2456 KiB
4Hibás válasz4ms2672 KiB
5Hibás válasz3ms2684 KiB
6Hibás válasz3ms2684 KiB
7Hibás válasz3ms2928 KiB
8Elfogadva3ms3144 KiB
subtask30/27
9Hibás válasz79ms3392 KiB
10Hibás válasz97ms3448 KiB
11Hibás válasz43ms3908 KiB
12Hibás válasz89ms3928 KiB
13Hibás válasz24ms3944 KiB
14Hibás válasz4ms4152 KiB
15Hibás válasz26ms4360 KiB
16Hibás válasz17ms4548 KiB
17Elfogadva35ms4452 KiB
subtask40/21
18Időlimit túllépés569ms5332 KiB
19Időlimit túllépés580ms6032 KiB
20Hibás válasz418ms8456 KiB
21Időlimit túllépés561ms8240 KiB
22Hibás válasz46ms10280 KiB
23Hibás válasz46ms11020 KiB
24Elfogadva14ms9792 KiB
subtask50/38
25Időlimit túllépés600ms19420 KiB
26Időlimit túllépés600ms21456 KiB
27Időlimit túllépés569ms23596 KiB
28Időlimit túllépés578ms25844 KiB
29Időlimit túllépés569ms24204 KiB
30Időlimit túllépés560ms26104 KiB
31Időlimit túllépés572ms28352 KiB
32Időlimit túllépés564ms30776 KiB
33Időlimit túllépés568ms32068 KiB
34Hibás válasz107ms29280 KiB
35Időlimit túllépés559ms32872 KiB
36Időlimit túllépés564ms35948 KiB
37Időlimit túllépés580ms38192 KiB
38Időlimit túllépés552ms38800 KiB
39Időlimit túllépés568ms45816 KiB
40Időlimit túllépés556ms45092 KiB
41Időlimit túllépés569ms46296 KiB
42Időlimit túllépés580ms45448 KiB
43Időlimit túllépés560ms49912 KiB
44Időlimit túllépés555ms52096 KiB