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

• 問題: No.3605 Grand Cross
• ユーザー: askr58
• 提出日時: 2026-07-25 06:06:52
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,937 bytes
• コンパイル時間: 1,827 ms
• コンパイル使用メモリ: 200,488 KB
• 実行使用メモリ: 39,808 KB
• 最終ジャッジ日時: 2026-07-31 20:51:35
• 合計ジャッジ時間: 9,662 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

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

ソースコード

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

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

using namespace std;

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;
    }

    int max_color = N + M;
    vector<vector<int>> I(max_color + 1);
    vector<vector<int>> J(max_color + 1);
    
    for (int i = 1; i <= N; ++i) {
        int c;
        cin >> c;
        I[c].push_back(i);
    }
    for (int j = 1; j <= M; ++j) {
        int d;
        cin >> d;
        J[d].push_back(j);
    }

    // 各インデックスの限界半径(lim)と、その限界まで広げたときの理論上最大スコア(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 - 1 - limA[i]];
    }
    for (int j = 1; j <= M; ++j) {
        limB[j] = min(j - 1, M - j);
        MaxB[j] = S_B[j + limB[j]] - S_B[j - 1 - limB[j]];
    }

    long long ans = -1;

    for (int c = 1; c <= max_color; ++c) {
        if (I[c].empty() || J[c].empty()) continue;

        // 【最重要最適化】: 探索前に ans の下界をヒューリスティックに一気に引き上げる
        // 1. Max（理論上最大スコア）が最大のペアを試す
        int best_max_i = I[c][0], best_max_j = J[c][0];
        for(int i : I[c]) if(MaxA[i] > MaxA[best_max_i]) best_max_i = i;
        for(int j : J[c]) if(MaxB[j] > MaxB[best_max_j]) best_max_j = j;
        
        int k1 = min(limA[best_max_i], limB[best_max_j]);
        long long val1 = (S_A[best_max_i + k1] - S_A[best_max_i - k1 - 1]) + (S_B[best_max_j + k1] - S_B[best_max_j - k1 - 1]);
        if (val1 > ans) ans = val1;

        // 2. 限界半径 (lim) が最大のペアを試す
        int best_lim_i = I[c][0], best_lim_j = J[c][0];
        for(int i : I[c]) if(limA[i] > limA[best_lim_i]) best_lim_i = i;
        for(int j : J[c]) if(limB[j] > limB[best_lim_j]) best_lim_j = j;
        
        int k2 = min(limA[best_lim_i], limB[best_lim_j]);
        long long val2 = (S_A[best_lim_i + k2] - S_A[best_lim_i - k2 - 1]) + (S_B[best_lim_j + k2] - S_B[best_lim_j - k2 - 1]);
        if (val2 > ans) ans = val2;

        // 理論上最大スコアの降順にソート
        sort(I[c].begin(), I[c].end(), [&](int a, int b) {
            return MaxA[a] > MaxA[b];
        });
        sort(J[c].begin(), J[c].end(), [&](int a, int b) {
            return MaxB[a] > MaxB[b];
        });

        // 枝刈り付き全探索 (Branch and Bound)
        for (int i : I[c]) {
            // A側の候補 i と、B側で最強の J[c][0] を組み合わせても ans 以下なら、完全終了
            if (MaxA[i] + MaxB[J[c][0]] <= ans) break;
            
            for (int j : J[c]) {
                // 現在の i, j の理論上の最大値が ans 以下なら、これ以降の弱い j を見ても無駄なので break
                if (MaxA[i] + MaxB[j] <= ans) break;
                
                int k = min(limA[i], limB[j]);
                long long sum = (S_A[i + k] - S_A[i - k - 1]) + (S_B[j + k] - S_B[j - k - 1]);
                
                if (sum > ans) {
                    ans = sum;
                }
            }
        }
    }

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

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}