52562023-04-24 12:14:30ZsofiaKeresztelyMágikus táblázatcpp14Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Time limit exceeded600ms2484 KiB
subtask20/14
3Wrong answer3ms2456 KiB
4Wrong answer4ms2672 KiB
5Wrong answer3ms2684 KiB
6Wrong answer3ms2684 KiB
7Wrong answer3ms2928 KiB
8Accepted3ms3144 KiB
subtask30/27
9Wrong answer79ms3392 KiB
10Wrong answer97ms3448 KiB
11Wrong answer43ms3908 KiB
12Wrong answer89ms3928 KiB
13Wrong answer24ms3944 KiB
14Wrong answer4ms4152 KiB
15Wrong answer26ms4360 KiB
16Wrong answer17ms4548 KiB
17Accepted35ms4452 KiB
subtask40/21
18Time limit exceeded569ms5332 KiB
19Time limit exceeded580ms6032 KiB
20Wrong answer418ms8456 KiB
21Time limit exceeded561ms8240 KiB
22Wrong answer46ms10280 KiB
23Wrong answer46ms11020 KiB
24Accepted14ms9792 KiB
subtask50/38
25Time limit exceeded600ms19420 KiB
26Time limit exceeded600ms21456 KiB
27Time limit exceeded569ms23596 KiB
28Time limit exceeded578ms25844 KiB
29Time limit exceeded569ms24204 KiB
30Time limit exceeded560ms26104 KiB
31Time limit exceeded572ms28352 KiB
32Time limit exceeded564ms30776 KiB
33Time limit exceeded568ms32068 KiB
34Wrong answer107ms29280 KiB
35Time limit exceeded559ms32872 KiB
36Time limit exceeded564ms35948 KiB
37Time limit exceeded580ms38192 KiB
38Time limit exceeded552ms38800 KiB
39Time limit exceeded568ms45816 KiB
40Time limit exceeded556ms45092 KiB
41Time limit exceeded569ms46296 KiB
42Time limit exceeded580ms45448 KiB
43Time limit exceeded560ms49912 KiB
44Time limit exceeded555ms52096 KiB