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

• 問題: No.3605 Grand Cross
• ユーザー: askr58
• 提出日時: 2026-07-25 05:48:23
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,554 bytes
• コンパイル時間: 1,594 ms
• コンパイル使用メモリ: 187,552 KB
• 実行使用メモリ: 38,272 KB
• 最終ジャッジ日時: 2026-07-31 20:51:23
• 合計ジャッジ時間: 9,594 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

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

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

    long long ans = -1;
    
    // メモリ確保のオーバーヘッドを無くすための使い回し配列
    vector<long long> temp_BestA(N + 1, -1);
    vector<long long> temp_BestB(M + 1, -1);
    vector<int> active_k_A;
    vector<int> active_k_B;

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

        // --- A の限界半径を基準にするケース ---
        for (int i : I[c]) {
            int k = min(i - 1, N - i);
            long long val = S_A[i + k] - S_A[i - 1 - k];
            if (temp_BestA[k] == -1) active_k_A.push_back(k);
            if (val > temp_BestA[k]) temp_BestA[k] = val;
        }

        for (int k : active_k_A) {
            long long mx_B = -1;
            // 条件を満たす j の範囲を二分探索で一発特定（if文を排除して高速化）
            auto it_start = lower_bound(J[c].begin(), J[c].end(), k + 1);
            auto it_end = upper_bound(J[c].begin(), J[c].end(), M - k);
            
            for (auto it = it_start; it < it_end; ++it) {
                int j = *it;
                long long val = S_B[j + k] - S_B[j - 1 - k];
                mx_B = mx_B > val ? mx_B : val;
            }
            if (mx_B != -1) {
                ans = max(ans, temp_BestA[k] + mx_B);
            }
        }

        // --- B の限界半径を基準にするケース ---
        for (int j : J[c]) {
            int k = min(j - 1, M - j);
            long long val = S_B[j + k] - S_B[j - 1 - k];
            if (temp_BestB[k] == -1) active_k_B.push_back(k);
            if (val > temp_BestB[k]) temp_BestB[k] = val;
        }

        for (int k : active_k_B) {
            long long mx_A = -1;
            auto it_start = lower_bound(I[c].begin(), I[c].end(), k + 1);
            auto it_end = upper_bound(I[c].begin(), I[c].end(), N - k);
            
            for (auto it = it_start; it < it_end; ++it) {
                int i = *it;
                long long val = S_A[i + k] - S_A[i - 1 - k];
                mx_A = mx_A > val ? mx_A : val;
            }
            if (mx_A != -1) {
                ans = max(ans, temp_BestB[k] + mx_A);
            }
        }

        // 使い回すため初期化（O(N) ではなく O(使用したkの数) で済む）
        for (int k : active_k_A) temp_BestA[k] = -1;
        active_k_A.clear();
        for (int k : active_k_B) temp_BestB[k] = -1;
        active_k_B.clear();
    }

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

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