結果

問題 No.3605 Grand Cross
コンテスト
ユーザー askr58
提出日時 2026-07-30 02:30:16
言語 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
結果
AC  
実行時間 139 ms / 2,000 ms
+ 666µs
コード長 2,957 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,189 ms
コンパイル使用メモリ 343,260 KB
実行使用メモリ 28,380 KB
最終ジャッジ日時 2026-07-31 20:53:12
合計ジャッジ時間 8,350 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//generated by ChatGPT

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int64 solve_left(
    const vector<int64>& A,
    const vector<int64>& B,
    const vector<int>& C,
    const vector<int>& D
) {
    const int N = static_cast<int>(A.size());
    const int M = static_cast<int>(B.size());
    const int color_count = N + M;

    // A 側で「左端までの距離」が最小になり得る位置。
    const int half = (N + 1) / 2;

    vector<vector<int>> positions(color_count + 1);

    for (int i = 1; i <= half; ++i) {
        positions[C[i - 1]].push_back(i);
    }

    vector<int64> prefixA(N + 1, 0);
    vector<int64> prefixB(M + 1, 0);

    for (int i = 1; i <= N; ++i) {
        prefixA[i] = prefixA[i - 1] + A[i - 1];
    }

    for (int i = 1; i <= M; ++i) {
        prefixB[i] = prefixB[i - 1] + B[i - 1];
    }

    int64 answer = -1;

    for (int j = 1; j <= M; ++j) {
        // i - 1 が4方向の距離の最小値になるための条件。
        const int limit = min({
            half,
            j,
            M - j + 1
        });

        const auto& v = positions[D[j - 1]];

        // limit 以下で最大の位置を求める。
        auto it = upper_bound(v.begin(), v.end(), limit);

        if (it == v.begin()) {
            continue;
        }

        --it;
        const int i = *it;
        const int length = 2 * i - 1;

        const int64 sumA = prefixA[length];

        // B[j-i+1 ... j+i-1]
        const int64 sumB =
            prefixB[j + i - 1] - prefixB[j - i];

        answer = max(answer, sumA + sumB);
    }

    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int N, M;
        cin >> N >> M;

        vector<int64> A(N), B(M);
        vector<int> C(N), D(M);

        for (auto& x : A) cin >> x;
        for (auto& x : B) cin >> x;
        for (auto& x : C) cin >> x;
        for (auto& x : D) cin >> x;

        vector<int64> reversedA = A;
        vector<int64> reversedB = B;
        vector<int> reversedC = C;
        vector<int> reversedD = D;

        reverse(reversedA.begin(), reversedA.end());
        reverse(reversedB.begin(), reversedB.end());
        reverse(reversedC.begin(), reversedC.end());
        reverse(reversedD.begin(), reversedD.end());

        int64 answer = -1;

        // A の左端が最初に当たる。
        answer = max(answer, solve_left(A, B, C, D));

        // A の右端が最初に当たる。
        answer = max(
            answer,
            solve_left(reversedA, reversedB, reversedC, reversedD)
        );

        // B の左端が最初に当たる。
        answer = max(answer, solve_left(B, A, D, C));

        // B の右端が最初に当たる。
        answer = max(
            answer,
            solve_left(reversedB, reversedA, reversedD, reversedC)
        );

        cout << answer << '\n';
    }
}
0