結果

問題 No.3605 Grand Cross
コンテスト
ユーザー askr58
提出日時 2026-07-25 05:54:23
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 3,060 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,843 ms
コンパイル使用メモリ 199,200 KB
実行使用メモリ 44,544 KB
最終ジャッジ日時 2026-07-31 20:51:32
合計ジャッジ時間 10,335 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 42 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//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> A(N + 1), B(M + 1);
    vector<long long> S_A(N + 1, 0), S_B(M + 1, 0);
    
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        S_A[i] = S_A[i - 1] + A[i];
    }
    for (int j = 1; j <= M; ++j) {
        cin >> B[j];
        S_B[j] = S_B[j - 1] + B[j];
    }

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

    // 色ごとにインデックスを分類
    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) I[C[i]].push_back(i);
    for (int j = 1; j <= M; ++j) J[D[j]].push_back(j);

    long long ans = -1;

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

        // 最大ポテンシャル (MaxA, MaxB) の降順にソートする
        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];
        });

        for (int i : I[c]) {
            // 【最強の枝刈り1】
            // i と、B側で最強のポテンシャルを持つ J[c][0] を組み合わせても ans 以下なら、
            // これ以降の i は絶対に ans を超えられないため終了
            if (MaxA[i] + MaxB[J[c][0]] <= ans) break;
            
            for (int j : J[c]) {
                // 【最強の枝刈り2】
                // i と現在の j の理論上の最大値が ans 以下なら、
                // これ以降の弱い j を見ても絶対に ans を超えられないため終了
                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;
}
0