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

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: sashiming
• 提出日時: 2026-05-02 17:53:09
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,925 bytes
• コンパイル時間: 7,270 ms
• コンパイル使用メモリ: 392,676 KB
• 実行使用メモリ: 6,400 KB
• スコア: 0
• 最終ジャッジ日時: 2026-05-02 17:55:02
• 合計ジャッジ時間: 105,640 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_1

ファイルパターン	結果
other	WA * 50

ソースコード

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
// #include<boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

using lnt = long long;
using Real = long double;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(lnt i=0;i<(n);++i)
#define RANGE(i, a, b) for(lnt i=(a);i<(b);++i)
#define RREP(i, n) for(lnt i=(n)-1;i>= 0;--i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define dcout cout<<fixed<<setprecision(20)
#define summon_tourist cin.tie(0);ios::sync_with_stdio(false)

constexpr int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
constexpr Real eps = 1e-9; const Real pi = acosl(-1);
constexpr lnt BIG = INT_MAX/10, BBIG = LLONG_MAX/10;

template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

using pint = pair<int, int>; using plnt = pair<lnt, lnt>;
using vint = vector<int>; using vlnt = vector<lnt>;
constexpr lnt MOD = 1e9+7;

int main(){
    summon_tourist;

    int N, T; cin >> N >> T;
    vector<vint> A(N, vint(N));
    REP(i, N) REP(j, N) cin >> A[i][j];

    auto st = chrono::steady_clock::now();
    const double LIMIT = 1.90;

    int bs = min(3, (int)sqrt(T));
    int mi, mj;
    int mx = -1;
    REP(i, N-bs+1) REP(j, N-bs+1) {
        int sum = 0;
        RANGE(k, i, i+bs) RANGE(l, j, j+bs) sum += A[k][l];
        if(chmax(mx, sum)) {
            mi = i; mj = j;
        }
    }
    const int dd[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
    mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

    vector<pint> cand;
    REP(i, N) REP(j, N) cand.emplace_back(A[i][j], i * N + j);
    sort(RALL(cand));
    int TOP = min<int>(50, (int)cand.size());

    vector<pint> best_path;
    long long best_total = -1;

    auto attempt = [&](int si, int sj){
        vector<pint> path;
        vector<vector<bool>> vis(N, vector<bool>(N, false));
        path.emplace_back(si, sj);
        vis[si][sj] = true;
        for(int step = 1; step < T; ++step){
            int ci = path.back().first, cj = path.back().second;
            vector<pair<int, pint>> nxt;
            for(int d = 0; d < 4; ++d){
                int ni = ci + dd[d][0], nj = cj + dd[d][1];
                if(ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
                if(vis[ni][nj]) continue;
                nxt.push_back({A[ni][nj], {ni, nj}});
            }
            if(nxt.empty()) break;
            sort(RALL(nxt));
            int pick = 0;
            if((int)nxt.size() >= 2 && (rng() & 1)) pick = 1;
            if((int)nxt.size() >= 3 && (rng() % 3 == 0)) pick = 2;
            auto [ni, nj] = nxt[pick].second;
            path.emplace_back(ni, nj);
            vis[ni][nj] = true;
        }
        long long total = 0;
        for(auto [i, j] : path) total += A[i][j];
        if(chmax(best_total, total)) best_path = move(path);
    };

    while(true){
        auto now = chrono::steady_clock::now();
        if(chrono::duration<double>(now - st).count() > LIMIT) break;
        int idx = rng() % TOP;
        int id = cand[idx].second;
        attempt(id / N, id % N);
        if((rng() & 7) == 0){
            int idx2 = rng() % TOP;
            int id2 = cand[idx2].second;
            attempt(id2 / N, id2 % N);
        }
    }

    cout << best_total << ln;
    cout << best_path.size() << ln;
    for(auto [i, j] : best_path) cout << i << ' ' << j << ln;
}