結果

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

ソースコード

diff #
raw source code 

#include <bits/extc++.h>

int main() {
    using namespace std;
    unsigned N, T;
    cin >> N >> T;
    vector A(N, vector<unsigned>(N));
    for (auto&& row : A)
        for (auto&& a : row)
            cin >> a;

    vector<vector<pair<unsigned, unsigned>>> idxs;

    // 横
    idxs.emplace_back();
    idxs.back().emplace_back(0, 0);
    for (unsigned i{}; i < N; i += 2) {
        ranges::copy(views::iota(1U, N) | views::transform([i](const auto j){return make_pair(i, j);}), back_inserter(idxs.back()));
        ranges::copy(views::iota(1U, N) | views::transform([i](const auto j){return make_pair(i + 1, j);}) | views::reverse, back_inserter(idxs.back()));
    }
    ranges::copy(views::iota(1U, N) | views::transform([](const auto i){return make_pair(i, 0);}) | views::reverse, back_inserter(idxs.back()));
    // 縦
    idxs.emplace_back();
    idxs.back().emplace_back(0, 0);
    for (unsigned i{}; i < N; i += 2) {
        ranges::copy(views::iota(1U, N) | views::transform([i](const auto j){return make_pair(j, i);}), back_inserter(idxs.back()));
        ranges::copy(views::iota(1U, N) | views::transform([i](const auto j){return make_pair(j, i + 1);}) | views::reverse, back_inserter(idxs.back()));
    }
    ranges::copy(views::iota(1U, N) | views::transform([](const auto i){return make_pair(0, i);}) | views::reverse, back_inserter(idxs.back()));

    const auto solve{[N, &A](const auto seq, unsigned T) {
        vector<unsigned> sum(N * N);
        for (const auto& [i, x] : seq | views::enumerate)
            sum[i] = A[x.first][x.second];
        for (unsigned i{}; i < N * N; ++i)
            sum.emplace_back(sum[i]);
        inclusive_scan(begin(sum), end(sum), begin(sum));
        sum.emplace(begin(sum));

        unsigned ans{}, now_idx{};
        for (unsigned i{}; i < N * N; ++i) {
            const auto now{sum[i + T] - sum[i]};
            if (now > ans) {
                ans = now;
                now_idx = i;
            }
        }
        vector<pair<unsigned, unsigned>> ret;
        ret.reserve(size(seq) * 2);
        ranges::copy(seq, back_inserter(ret));
        ranges::copy(seq, back_inserter(ret));
        return make_pair(ans, ret | views::drop(now_idx) | views::take(T) | ranges::to<vector>());
    }};

    const auto [ans, seq]{ranges::max(idxs | views::transform([T, &solve](const auto& r){return solve(r, T);}))};

    cout << size(seq) << endl;
    for (const auto& [i, j] : seq)
        cout << i << " " << j << endl;
    return 0;
}
0