제출 #1350475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1350475		Faisal_Saqib	Domino (COCI15_domino)	C++20	0 / 160	4100 ms	147604 KiB

domino

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

typedef long long ll;

struct Edge {
    int u, v;
    ll w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<vector<int>> a(n, vector<int>(n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> a[i][j];

    vector<Edge> edges;

    auto id = [&](int i, int j) {
        return i * n + j;
    };

    // only right and down (avoid duplicates)
    int dx[2] = {1, 0};
    int dy[2] = {0, 1};

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int d = 0; d < 2; d++) {
                int ni = i + dx[d];
                int nj = j + dy[d];
                if(ni >= n || nj >= n) continue;

                edges.push_back({
                    id(i,j),
                    id(ni,nj),
                    (ll)a[i][j] + a[ni][nj]
                });
            }
        }
    }

    // sort descending
    sort(edges.begin(), edges.end(), [](auto &A, auto &B){
        return A.w > B.w;
    });

    // keep only top edges (IMPORTANT)
    int LIMIT = min((int)edges.size(), 120);
    edges.resize(LIMIT);

    int E = edges.size();

    vector<char> used(n*n, 0);

    ll ans = 0;

    // prefix max sum for pruning
    vector<ll> pref(E+1, 0);
    for(int i = E-1; i >= 0; i--) {
        pref[i] = pref[i+1] + edges[i].w;
    }

    function<void(int,int,ll)> dfs = [&](int idx, int taken, ll sum) {
        if(taken == k || idx == E) {
            ans = max(ans, sum);
            return;
        }

        // pruning
        if(sum + pref[idx] <= ans) return;

        // skip this edge
        dfs(idx+1, taken, sum);

        // take this edge if possible
        auto &e = edges[idx];
        if(!used[e.u] && !used[e.v]) {
            used[e.u] = used[e.v] = 1;
            dfs(idx+1, taken+1, sum + e.w);
            used[e.u] = used[e.v] = 0;
        }
    };

    dfs(0, 0, 0);

    cout << ans << "\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10
• Subtask 16: 0 / 10