#1149612 (C++23) No.2509 Beam Shateki

• 問題: No.2509 Beam Shateki
• ユーザー: D M
• 提出日時: 2026-02-27 10:07:59
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 3,044 bytes
• コンパイル時間: 3,448 ms
• コンパイル使用メモリ: 345,792 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-02-27 10:08:05
• 合計ジャッジ時間: 6,035 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

ファイルパターン	結果
sample	AC * 3
other	AC * 61

ソースコード

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

using ll = long long;

struct Line {
    int type; // 0: row, 1: col, 2: diag(i-j), 3: diag(i+j)
    int p;    // 種類ごとのパラメータ
    ll sum;
};

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

    int H, W;
    cin >> H >> W;

    vector<vector<ll>> A(H + 1, vector<ll>(W + 1, 0));

    vector<ll> row(H + 1, 0), col(W + 1, 0);
    vector<ll> diag1(H + W - 1, 0); // index = (i-j) + (W-1)
    vector<ll> diag2(H + W + 1, 0); // index = i+j をそのまま使う

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> A[i][j];
            ll v = A[i][j];
            row[i] += v;
            col[j] += v;
            diag1[i - j + (W - 1)] += v;
            diag2[i + j] += v;
        }
    }

    vector<Line> lines;
    lines.reserve(3 * H + 3 * W - 2);

    // 行
    for (int i = 1; i <= H; i++) {
        lines.push_back({0, i, row[i]});
    }

    // 列
    for (int j = 1; j <= W; j++) {
        lines.push_back({1, j, col[j]});
    }

    // i-j が一定の対角線
    for (int k = -(W - 1); k <= H - 1; k++) {
        lines.push_back({2, k, diag1[k + (W - 1)]});
    }

    // i+j が一定の対角線
    for (int s = 2; s <= H + W; s++) {
        lines.push_back({3, s, diag2[s]});
    }

    auto overlap = [&](const Line& x, const Line& y) -> ll {
        Line a = x, b = y;
        if (a.type > b.type) swap(a, b);

        // 同じ種類の異なる直線は交わらない
        if (a.type == b.type) return 0;

        int r = -1, c = -1;

        if (a.type == 0 && b.type == 1) {
            // row r, col c
            r = a.p;
            c = b.p;
        } else if (a.type == 0 && b.type == 2) {
            // row r, diag i-j=k -> c = r-k
            r = a.p;
            c = r - b.p;
        } else if (a.type == 0 && b.type == 3) {
            // row r, anti-diag i+j=s -> c = s-r
            r = a.p;
            c = b.p - r;
        } else if (a.type == 1 && b.type == 2) {
            // col c, diag i-j=k -> r = c+k
            c = a.p;
            r = c + b.p;
        } else if (a.type == 1 && b.type == 3) {
            // col c, anti-diag i+j=s -> r = s-c
            c = a.p;
            r = b.p - c;
        } else if (a.type == 2 && b.type == 3) {
            // i-j=k, i+j=s
            int k = a.p, s = b.p;
            if ((s + k) & 1) return 0; // 整数解なし
            r = (s + k) / 2;
            c = (s - k) / 2;
        }

        if (1 <= r && r <= H && 1 <= c && c <= W) {
            return A[r][c];
        }
        return 0;
    };

    ll ans = 0;

    // 1本だけ使う場合
    for (const auto& ln : lines) {
        ans = max(ans, ln.sum);
    }

    // 2本使う場合
    int L = (int)lines.size();
    for (int i = 0; i < L; i++) {
        for (int j = i + 1; j < L; j++) {
            ll cand = lines[i].sum + lines[j].sum - overlap(lines[i], lines[j]);
            ans = max(ans, cand);
        }
    }

    cout << ans << '\n';
    return 0;
}