#1174229 (C++23) No.3605 Grand Cross

• 問題: No.3605 Grand Cross
• ユーザー: askr58
• 提出日時: 2026-07-30 00:51:22
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 4,034 bytes
• コンパイル時間: 2,325 ms
• コンパイル使用メモリ: 352,484 KB
• 実行使用メモリ: 42,216 KB
• 最終ジャッジ日時: 2026-07-31 20:52:39
• 合計ジャッジ時間: 20,650 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 43 WA * 6

ソースコード

//generated by ChatGPT

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

// コンパイル時に -DHEURISTIC_K=500 などで変更可能
#ifndef HEURISTIC_K
#define HEURISTIC_K 1000
#endif

/*
 * v の中から
 *   1. 配列中央に近い HEURISTIC_K 個
 *   2. 値が大きい HEURISTIC_K 個
 * を候補として選ぶ。
 */
static vector<char> choose_candidates(const vector<int64>& v) {
    const int n = static_cast<int>(v.size());
    const int take = min(n, HEURISTIC_K);

    vector<char> selected(n, false);
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);

    // 2倍した中央からの距離。
    // abs(i - (n-1)/2) の小数を避けたもの。
    auto center_distance = [n](int i) {
        return abs(2 * i - (n - 1));
    };

    // 中央に近い順
    sort(order.begin(), order.end(), [&](int i, int j) {
        int di = center_distance(i);
        int dj = center_distance(j);

        if (di != dj) return di < dj;
        if (v[i] != v[j]) return v[i] > v[j];
        return i < j;
    });

    for (int t = 0; t < take; ++t) {
        selected[order[t]] = true;
    }

    // 値が大きい順
    sort(order.begin(), order.end(), [&](int i, int j) {
        if (v[i] != v[j]) return v[i] > v[j];

        int di = center_distance(i);
        int dj = center_distance(j);

        if (di != dj) return di < dj;
        return i < j;
    });

    for (int t = 0; t < take; ++t) {
        selected[order[t]] = true;
    }

    return selected;
}

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

    int T;
    cin >> T;

    while (T--) {
        int N, M;
        cin >> N >> M;

        vector<int64> A(N), B(M);
        vector<int> C(N), D(M);

        for (int64& x : A) cin >> x;
        for (int64& x : B) cin >> x;
        for (int& x : C) cin >> x;
        for (int& x : D) cin >> x;

        vector<int64> prefixA(N + 1, 0);
        vector<int64> prefixB(M + 1, 0);

        for (int i = 0; i < N; ++i) {
            prefixA[i + 1] = prefixA[i] + A[i];
        }

        for (int j = 0; j < M; ++j) {
            prefixB[j + 1] = prefixB[j] + B[j];
        }

        vector<int> radiusA(N);
        vector<int> radiusB(M);

        for (int i = 0; i < N; ++i) {
            radiusA[i] = min(i, N - 1 - i);
        }

        for (int j = 0; j < M; ++j) {
            radiusB[j] = min(j, M - 1 - j);
        }

        vector<char> candidateA = choose_candidates(A);
        vector<char> candidateB = choose_candidates(B);

        const int colorCount = N + M;

        vector<vector<int>> positionsA(colorCount + 1);
        vector<vector<int>> positionsB(colorCount + 1);

        for (int i = 0; i < N; ++i) {
            positionsA[C[i]].push_back(i);
        }

        for (int j = 0; j < M; ++j) {
            positionsB[D[j]].push_back(j);
        }

        int64 answer = -1;

        auto evaluate = [&](int i, int j) {
            int radius = min(radiusA[i], radiusB[j]);

            int64 sumA =
                prefixA[i + radius + 1] -
                prefixA[i - radius];

            int64 sumB =
                prefixB[j + radius + 1] -
                prefixB[j - radius];

            answer = max(answer, sumA + sumB);
        };

        /*
         * A の候補中心 × B の同色な全中心
         */
        for (int i = 0; i < N; ++i) {
            if (!candidateA[i]) continue;

            for (int j : positionsB[C[i]]) {
                evaluate(i, j);
            }
        }

        /*
         * B の候補中心 × A の同色な全中心
         *
         * candidateA[i] も真の場合、その組は上で評価済みなので
         * 重複を避けるため除外する。
         */
        for (int j = 0; j < M; ++j) {
            if (!candidateB[j]) continue;

            for (int i : positionsA[D[j]]) {
                if (candidateA[i]) continue;
                evaluate(i, j);
            }
        }

        cout << answer << '\n';
    }

    return 0;
}