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

• 問題: No.3605 Grand Cross
• ユーザー: askr58
• 提出日時: 2026-07-25 05:32:21
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,547 bytes
• コンパイル時間: 1,183 ms
• コンパイル使用メモリ: 179,040 KB
• 実行使用メモリ: 41,344 KB
• 最終ジャッジ日時: 2026-07-31 20:51:15
• 合計ジャッジ時間: 11,733 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

//generated by Gemini
#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);
    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int j = 1; j <= M; ++j) cin >> 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];

    // 1. 累積和の計算 (1-indexed)
    vector<long long> S_A(N + 1, 0), S_B(M + 1, 0);
    for (int i = 1; i <= N; ++i) S_A[i] = S_A[i - 1] + A[i];
    for (int j = 1; j <= M; ++j) S_B[j] = S_B[j - 1] + B[j];

    // 2. 各インデックスの中心からの限界半径 lim を計算
    vector<int> limA(N + 1), limB(M + 1);
    for (int i = 1; i <= N; ++i) limA[i] = min(i - 1, N - i);
    for (int j = 1; j <= M; ++j) limB[j] = min(j - 1, M - j);

    // 3. 各色ごとにインデックスをグループ分け
    int max_color = N + M;
    vector<vector<int>> I(max_color + 1), J(max_color + 1);
    for (int i = 1; i <= N; ++i) {
        if (C[i] <= max_color) I[C[i]].push_back(i);
    }
    for (int j = 1; j <= M; ++j) {
        if (D[j] <= max_color) J[D[j]].push_back(j);
    }

    long long ans = -1;

    // 4. 各色について処理
    for (int c = 1; c <= max_color; ++c) {
        if (I[c].empty() || J[c].empty()) continue;

        // 方法1と方法2の推定計算量を比較
        long long cost1 = (long long)I[c].size() * J[c].size();

        long long cost2_A = 0;
        for (int i : I[c]) cost2_A += limA[i];
        long long cost2_B = 0;
        for (int j : J[c]) cost2_B += limB[j];
        long long cost2 = cost2_A + cost2_B;

        if (cost1 <= cost2) {
            // 【方法1】 全ペア探索
            for (int i : I[c]) {
                for (int j : J[c]) {
                    int k = min(limA[i], limB[j]);
                    long long valA = S_A[i + k] - S_A[i - 1 - k];
                    long long valB = S_B[j + k] - S_B[j - 1 - k];
                    ans = max(ans, valA + valB);
                }
            }
        } else {
            // 【方法2】 半径 k ごとの最大値配列を構築して合成
            int max_lim_A = 0;
            for (int i : I[c]) max_lim_A = max(max_lim_A, limA[i]);
            int max_lim_B = 0;
            for (int j : J[c]) max_lim_B = max(max_lim_B, limB[j]);

            int max_k = min(max_lim_A, max_lim_B);

            vector<long long> f_A(max_k + 1, -1);
            for (int i : I[c]) {
                int L = min(limA[i], max_k);
                for (int k = 0; k <= L; ++k) {
                    long long val = S_A[i + k] - S_A[i - 1 - k];
                    f_A[k] = max(f_A[k], val);
                }
            }

            vector<long long> f_B(max_k + 1, -1);
            for (int j : J[c]) {
                int L = min(limB[j], max_k);
                for (int k = 0; k <= L; ++k) {
                    long long val = S_B[j + k] - S_B[j - 1 - k];
                    f_B[k] = max(f_B[k], val);
                }
            }

            for (int k = 0; k <= max_k; ++k) {
                if (f_A[k] != -1 && f_B[k] != -1) {
                    ans = max(ans, f_A[k] + f_B[k]);
                }
            }
        }
    }

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

int main() {
    // 高速入出力設定
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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