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

• 問題: No.3605 Grand Cross
• ユーザー: askr58
• 提出日時: 2026-07-25 06:12:11
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,115 bytes
• コンパイル時間: 2,120 ms
• コンパイル使用メモリ: 217,588 KB
• 実行使用メモリ: 50,688 KB
• 最終ジャッジ日時: 2026-07-31 20:51:44
• 合計ジャッジ時間: 10,305 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 42 TLE * 1 -- * 6

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 高速化のため、使い回す集計配列はグローバルに確保
const int MAXK = 200005;
long long mxA[MAXK];
long long mxB[MAXK];

void solve() {
    int N, M;
    if (!(cin >> N >> M)) return;

    // 累積和の構築 (1-indexed)
    vector<long long> S_A(N + 1, 0), S_B(M + 1, 0);
    for (int i = 1; i <= N; ++i) {
        long long a; cin >> a;
        S_A[i] = S_A[i - 1] + a;
    }
    for (int j = 1; j <= M; ++j) {
        long long b; cin >> b;
        S_B[j] = S_B[j - 1] + b;
    }

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

    // 各インデックスの限界半径と、その限界まで伸ばした時の絶対最大ポテンシャル (Max)
    vector<int> limA(N + 1), limB(M + 1);
    vector<long long> MaxA(N + 1), MaxB(M + 1);

    for (int i = 1; i <= N; ++i) {
        limA[i] = min(i - 1, N - i);
        MaxA[i] = S_A[i + limA[i]] - S_A[i - limA[i] - 1];
    }
    for (int j = 1; j <= M; ++j) {
        limB[j] = min(j - 1, M - j);
        MaxB[j] = S_B[j + limB[j]] - S_B[j - limB[j] - 1];
    }

    int max_color = N + M;
    vector<vector<int>> I(max_color + 1);
    vector<vector<int>> J(max_color + 1);
    vector<long long> max_pot_A(max_color + 1, -1);
    vector<long long> max_pot_B(max_color + 1, -1);

    for (int i = 1; i <= N; ++i) {
        I[C[i]].push_back(i);
        if (MaxA[i] > max_pot_A[C[i]]) max_pot_A[C[i]] = MaxA[i];
    }
    for (int j = 1; j <= M; ++j) {
        J[D[j]].push_back(j);
        if (MaxB[j] > max_pot_B[D[j]]) max_pot_B[D[j]] = MaxB[j];
    }

    long long ans = -1;

    // 1. 本格的な探索の前に、ans の下界を一気に引き上げる
    for (int c = 1; c <= max_color; ++c) {
        if (I[c].empty() || J[c].empty()) continue;
        
        // (A) 最強ポテンシャル同士のペア
        int best_i = I[c][0], best_j = J[c][0];
        for (int i : I[c]) if (MaxA[i] > MaxA[best_i]) best_i = i;
        for (int j : J[c]) if (MaxB[j] > MaxB[best_j]) best_j = j;
        int k1 = min(limA[best_i], limB[best_j]);
        long long val1 = (S_A[best_i + k1] - S_A[best_i - k1 - 1]) + (S_B[best_j + k1] - S_B[best_j - k1 - 1]);
        if (val1 > ans) ans = val1;

        // (B) 限界半径が最大同士のペア
        int max_lim_i = I[c][0], max_lim_j = J[c][0];
        for (int i : I[c]) if (limA[i] > limA[max_lim_i]) max_lim_i = i;
        for (int j : J[c]) if (limB[j] > limB[max_lim_j]) max_lim_j = j;
        int k2 = min(limA[max_lim_i], limB[max_lim_j]);
        long long val2 = (S_A[max_lim_i + k2] - S_A[max_lim_i - k2 - 1]) + (S_B[max_lim_j + k2] - S_B[max_lim_j - k2 - 1]);
        if (val2 > ans) ans = val2;
    }

    // 2. 徹底的なフィルタリングとハイブリッド最適化探索
    for (int c = 1; c <= max_color; ++c) {
        if (I[c].empty() || J[c].empty()) continue;

        // 【最強の最適化】絶対に ans を超えられない弱いインデックスを物理的に削除する
        vector<int> fI, fJ;
        for (int i : I[c]) {
            if (MaxA[i] + max_pot_B[c] > ans) fI.push_back(i);
        }
        for (int j : J[c]) {
            if (MaxB[j] + max_pot_A[c] > ans) fJ.push_back(j);
        }

        if (fI.empty() || fJ.empty()) continue;

        // 計算量の見積もり
        long long cost1 = (long long)fI.size() * fJ.size();
        
        int max_k_A = 0, max_k_B = 0;
        for (int i : fI) if (limA[i] > max_k_A) max_k_A = limA[i];
        for (int j : fJ) if (limB[j] > max_k_B) max_k_B = limB[j];
        int max_k = min(max_k_A, max_k_B);

        long long cost2 = 0;
        for (int i : fI) cost2 += min(limA[i], max_k) + 1;
        for (int j : fJ) cost2 += min(limB[j], max_k) + 1;

        if (cost1 <= cost2) {
            // 【方法1】 ペア全探索 ＋ 枝刈り (少数の強要素向け)
            sort(fI.begin(), fI.end(), [&](int a, int b) { return MaxA[a] > MaxA[b]; });
            sort(fJ.begin(), fJ.end(), [&](int a, int b) { return MaxB[a] > MaxB[b]; });

            for (int i : fI) {
                if (MaxA[i] + MaxB[fJ[0]] <= ans) break;
                for (int j : fJ) {
                    if (MaxA[i] + MaxB[j] <= ans) break;
                    int k = min(limA[i], limB[j]);
                    long long val = (S_A[i + k] - S_A[i - k - 1]) + (S_B[j + k] - S_B[j - k - 1]);
                    if (val > ans) ans = val;
                }
            }
        } else {
            // 【方法2】 半径ベースの集計配列構築 (多数の要素向け)
            for (int i : fI) {
                int lim = min(limA[i], max_k);
                for (int k = 0; k <= lim; ++k) {
                    long long val = S_A[i + k] - S_A[i - k - 1];
                    if (val > mxA[k]) mxA[k] = val;
                }
            }
            for (int j : fJ) {
                int lim = min(limB[j], max_k);
                for (int k = 0; k <= lim; ++k) {
                    long long val = S_B[j + k] - S_B[j - k - 1];
                    if (val > mxB[k]) mxB[k] = val;
                }
            }
            // 答えの統合と配列の初期化 (再利用のため O(K) でクリア)
            for (int k = 0; k <= max_k; ++k) {
                if (mxA[k] != -1 && mxB[k] != -1) {
                    long long sum = mxA[k] + mxB[k];
                    if (sum > ans) ans = sum;
                }
                mxA[k] = -1;
                mxB[k] = -1;
            }
        }
    }

    cout << ans << "\n";
}

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // グローバル配列の初期化 (プログラム実行時に1度だけ)
    for (int i = 0; i < MAXK; ++i) {
        mxA[i] = -1;
        mxB[i] = -1;
    }

    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}