Submission #1348215

#TimeUsernameProblemLanguageResultExecution timeMemory
1348215killerzaluuCount Squares (CEOI19_countsquares)C++20
100 / 100
229 ms107132 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int h, v;
    cin >> h >> v;

    int y[1505], x[1505];
    for (int i = 0; i < h; i++) cin >> y[i];
    for (int i = 0; i < v; i++) cin >> x[i];

    unordered_map<int, long long> a, b;
    a.reserve((long long)h * h);
    b.reserve((long long)v * v);
    a.max_load_factor(0.7);
    b.max_load_factor(0.7);

    for (int i = 0; i < h; i++) {
        for (int j = i + 1; j < h; j++) {
            a[y[j] - y[i]]++;
        }
    }

    for (int i = 0; i < v; i++) {
        for (int j = i + 1; j < v; j++) {
            b[x[j] - x[i]]++;
        }
    }

    long long ans = 0;
    if (a.size() > b.size()) swap(a, b);

    for (auto &it : a) {
        auto p = b.find(it.first);
        if (p != b.end()) ans += it.second * p->second;
    }

    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...