#1162578 (C++17) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: naka9
• 提出日時: 2026-05-02 17:50:21
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,584 bytes
• コンパイル時間: 896 ms
• コンパイル使用メモリ: 102,596 KB
• 実行使用メモリ: 6,400 KB
• スコア: 1,001,431
• 最終ジャッジ日時: 2026-05-02 17:50:43
• 合計ジャッジ時間: 8,222 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
other	AC * 37 WA * 13

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, T;
    cin >> N >> T;

    vector<vector<int>> A(N, vector<int>(N));
    vector<vector<int>> S(N + 1, vector<int>(N + 1, 0)); // 累積和

    // 累積和の構築 (2次元)
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
            // S[i+1][j+1] は (0,0)から(i,j)までの矩形和
            S[i + 1][j + 1] = S[i][j + 1] + S[i + 1][j] - S[i][j] + A[i][j];
        }
    }

    int maxsum = -2e9; // 負の値もあり得るため初期化に注意
    int mxl = 0, mxr = 0, myl = 0, myr = 0;

    // 縦*横がTを超えない長方形について、総和が最大になるものを求める
    for (int xl = 0; xl < N; xl++) {
        for (int xr = xl; xr < N; xr++) {
            for (int yl = 0; yl < N; yl++) {
                for (int yr = yl; yr < N; yr++) {
                    int width = (xr - xl + 1);
                    int height = (yr - yl + 1);
                    if (width * height > T) {
                        break; // これ以上yrを大きくしてもTを超えるため
                    }

                    // 指定された累積和の公式: 右下 - 右上 - 左下 + 左上
                    int sum = S[xr + 1][yr + 1] - S[xl][yr + 1] - S[xr + 1][yl] + S[xl][yl];

                    if (sum > maxsum) {
                        maxsum = sum;
                        mxl = xl; mxr = xr;
                        myl = yl; myr = yr;
                    }
                }
            }
        }
    }

    vector<pair<int, int>> path;
    int rect_size = (mxr - mxl + 1) * (myr - myl + 1);
    int extra = T - rect_size;

    // 指示に基づき、下にスペースがない場合の事前パス構築
    if (myr == N - 1 && extra > 0) {
        // 左上の頂点(mxl, myl)に行く前に、右から左へ辿るパスを追加
        // 枠内(0..N-1)に収まるよう調整
        int cur_x = mxl;
        int cur_y = myl - 1;
        for (int k = 0; k < extra; k++) {
            if (cur_y < 0) { // 左端に達したら上の行へ（念のための枠外回避）
                cur_x = max(0, cur_x - 1);
                cur_y = 0;
            }
            path.push_back({cur_x, cur_y});
            if (cur_y > 0) cur_y--;
        }
        // 事前追加なので反転して「左上の頂点に行く直前」の形にする
        reverse(path.begin(), path.end());
    }

    // 長方形内を蛇行して辿る
    for (int i = mxl; i <= mxr; i++) {
        if ((i - mxl) % 2 == 0) {
            for (int j = myl; j <= myr; j++) {
                path.push_back({i, j});
            }
        } else {
            for (int j = myr; j >= myl; j--) {
                path.push_back({i, j});
            }
        }
    }

    // 指示に基づき、下にスペースがある場合に蛇行を継続
    if (myr < N - 1) {
        int cur_x = mxr + 1;
        while (path.size() < T && cur_x < N) {
            if ((cur_x - mxl) % 2 == 0) {
                for (int j = myl; j <= myr && path.size() < T; j++) {
                    path.push_back({cur_x, j});
                }
            } else {
                for (int j = myr; j >= myl && path.size() < T; j--) {
                    path.push_back({cur_x, j});
                }
            }
            cur_x++;
        }
    }

    // 最終出力
    cout << path.size() << endl;
    for (const auto& p : path) {
        cout << p.first << " " << p.second << endl;
    }

    return 0;
}