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

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

ファイルパターン	結果
sample	WA * 1
other	WA * 34 RE * 15

ソースコード

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

using int64 = long long;

constexpr int DEFAULT_K = 1000;

/*
候補集合を作る。

1. 列の中央に近い位置を K 個
2. 値が大きい位置を K 個

添字は 1-indexed。
*/
vector<int> buildCandidates(
    const vector<int64>& values,
    int K
) {
    int n = static_cast<int>(values.size()) - 1;

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

    // 中央との距離は |2*i - (n+1)| で比較できる。
    sort(order.begin(), order.end(), [&](int i, int j) {
        int64 distI = abs(2LL * i - (n + 1LL));
        int64 distJ = abs(2LL * j - (n + 1LL));

        if (distI != distJ) return distI < distJ;
        return i < j;
    });

    for (int t = 0; t < min(K, n); ++t) {
        selected[order[t]] = true;
    }

    // 単体の値が大きい位置を選ぶ。
    sort(order.begin(), order.end(), [&](int i, int j) {
        if (values[i] != values[j]) {
            return values[i] > values[j];
        }
        return i < j;
    });

    for (int t = 0; t < min(K, n); ++t) {
        selected[order[t]] = true;
    }

    vector<int> candidates;
    candidates.reserve(min(n, 2 * K));

    for (int i = 1; i <= n; ++i) {
        if (selected[i]) {
            candidates.push_back(i);
        }
    }

    return candidates;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    /*
    ローカル実行時には

        ./main 500

    のようにして K を変更できる。
    引数を指定しなければ K=1000。
    */
    int K = DEFAULT_K;

    if (argc >= 2) {
        K = stoi(argv[1]);
    }

    int N, M;
    cin >> N >> M;

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

    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int j = 1; j <= M; ++j) cin >> B[j];
    for (int i = 1; i <= N; ++i) cin >> C[i];
    for (int j = 1; j <= M; ++j) cin >> D[j];

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

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

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

    vector<int> candidatesA = buildCandidates(A, K);
    vector<int> candidatesB = buildCandidates(B, K);

    vector<char> selectedA(N + 1, false);
    vector<char> selectedB(M + 1, false);

    for (int i : candidatesA) selectedA[i] = true;
    for (int j : candidatesB) selectedB[j] = true;

    const int maxColor = N + M;

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

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

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

    auto rangeSumA = [&](int left, int right) -> int64 {
        return prefixA[right] - prefixA[left - 1];
    };

    auto rangeSumB = [&](int left, int right) -> int64 {
        return prefixB[right] - prefixB[left - 1];
    };

    auto calculateScore = [&](int i, int j) -> int64 {
        int radius = min({
            i - 1,
            N - i,
            j - 1,
            M - j
        });

        return rangeSumA(i - radius, i + radius)
             + rangeSumB(j - radius, j + radius);
    };

    int64 answer = -1;

    /*
    A 側の候補中心と、B 側の同色中心をすべて組み合わせる。
    */
    for (int i : candidatesA) {
        int color = C[i];

        for (int j : positionsB[color]) {
            answer = max(answer, calculateScore(i, j));
        }
    }

    /*
    B 側の候補中心と、A 側の同色中心をすべて組み合わせる。

    A 側も候補である組は上で計算済みなので除外する。
    これは答えには影響せず、重複計算だけを減らす。
    */
    for (int j : candidatesB) {
        int color = D[j];

        for (int i : positionsA[color]) {
            if (selectedA[i]) continue;

            answer = max(answer, calculateScore(i, j));
        }
    }

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