結果

問題 No.5024 魔法少女うなと宝集め
コンテスト
ユーザー naka9
提出日時 2026-05-02 17:53:28
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,212 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 895 ms
コンパイル使用メモリ 101,124 KB
実行使用メモリ 6,400 KB
スコア 1,630,724
最終ジャッジ日時 2026-05-02 17:53:37
合計ジャッジ時間 6,361 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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);


    // 長方形内を蛇行して辿る
    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});
            }
        }
    }

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

    return 0;
}
0