52582023-04-24 12:32:09ZsofiaKeresztelyMágikus táblázatcpp14Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1812 KiB
2Time limit exceeded600ms1768 KiB
subtask20/14
3Wrong answer3ms2220 KiB
4Wrong answer3ms2608 KiB
5Wrong answer3ms2676 KiB
6Wrong answer3ms2768 KiB
7Wrong answer3ms2844 KiB
8Accepted3ms3036 KiB
subtask30/27
9Wrong answer81ms3372 KiB
10Wrong answer94ms3436 KiB
11Wrong answer43ms3396 KiB
12Wrong answer128ms3276 KiB
13Wrong answer32ms3352 KiB
14Wrong answer6ms3500 KiB
15Wrong answer27ms3888 KiB
16Wrong answer19ms4132 KiB
17Accepted35ms4048 KiB
subtask40/21
18Time limit exceeded550ms3992 KiB
19Time limit exceeded560ms4280 KiB
20Time limit exceeded541ms5580 KiB
21Time limit exceeded577ms4528 KiB
22Wrong answer46ms5780 KiB
23Wrong answer45ms5536 KiB
24Accepted14ms4460 KiB
subtask50/38
25Time limit exceeded600ms8364 KiB
26Time limit exceeded555ms8436 KiB
27Time limit exceeded541ms8304 KiB
28Time limit exceeded600ms8276 KiB
29Time limit exceeded560ms8516 KiB
30Time limit exceeded561ms8536 KiB
31Time limit exceeded545ms8460 KiB
32Time limit exceeded552ms7224 KiB
33Time limit exceeded560ms7256 KiB
34Time limit exceeded560ms4448 KiB
35Time limit exceeded555ms6576 KiB
36Time limit exceeded577ms8708 KiB
37Time limit exceeded568ms9216 KiB
38Time limit exceeded551ms8476 KiB
39Time limit exceeded552ms9116 KiB
40Time limit exceeded555ms9664 KiB
41Time limit exceeded555ms8520 KiB
42Time limit exceeded560ms7308 KiB
43Time limit exceeded564ms7456 KiB
44Time limit exceeded580ms7472 KiB