提出 bdd72375-668a-4b9a-962d-7724209427c6

コード

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

struct Op {
    int H, W, a, b;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, T;
    if (!(cin >> N >> T)) return 0;
    vector<vector<int>> A(N, vector<int>(N)), B(N, vector<int>(N));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) cin >> A[i][j];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) cin >> B[i][j];
    vector<Op> ops(T);
    for (int t = 0; t < T; ++t) {
        cin >> ops[t].H >> ops[t].W >> ops[t].a >> ops[t].b;
    }

    const int LIMIT = 100000;
    vector<tuple<int,int,int>> out;
    out.reserve(10000);

    for (int t = 0; t < T; ++t) {
        int H = ops[t].H, W = ops[t].W, a = ops[t].a, b = ops[t].b;
        int uses = 0;
        while (uses < 3 && (int)out.size() < LIMIT) {
            vector<vector<ll>> pref(N+1, vector<ll>(N+1, 0));
            bool anyPossible = false;
            for (int i = 0; i < N; ++i) {
                ll rowSum = 0;
                for (int j = 0; j < N; ++j) {
                    ll w = 0;
                    if (A[i][j] == a) {
                        ll before = (ll)A[i][j] - (ll)B[i][j];
                        ll after = (ll)b - (ll)B[i][j];
                        w = after*after - before*before;
                        anyPossible = true;
                    }
                    rowSum += w;
                    pref[i+1][j+1] = pref[i][j+1] + rowSum;
                }
            }
            if (!anyPossible) break;
            ll bestDelta = 0;
            int bestX = -1, bestY = -1;
            for (int x = 0; x + H <= N; ++x) {
                for (int y = 0; y + W <= N; ++y) {
                    int x2 = x + H, y2 = y + W;
                    ll s = pref[x2][y2] - pref[x][y2] - pref[x2][y] + pref[x][y];
                    if (s < bestDelta) {
                        bestDelta = s;
                        bestX = x;
                        bestY = y;
                    }
                }
            }
            if (bestX == -1) break;
            for (int i = bestX; i < bestX + H; ++i) {
                for (int j = bestY; j < bestY + W; ++j) {
                    if (A[i][j] == a) A[i][j] = b;
                }
            }
            out.emplace_back(t, bestX, bestY);
            ++uses;
        }
        if ((int)out.size() >= LIMIT) break;
    }

    cout << out.size() << '\n';
    for (auto &tp : out) {
        int id, x, y;
        tie(id, x, y) = tp;
        cout << id << " " << x << " " << y << "\n";
    }
    return 0;
}
結果

問題	点数	言語	結果	実行時間	メモリ
A - Replace() は Replace() されました	86584986	C++	AC	39 ms	4036 KiB