Submission #1239276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239276		sah	Domino (COCI15_domino)	C++17	160 / 160	658 ms	141396 KiB

domino

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

using ll = long long;

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

int N, K;
vector<ll> used;
vector<Edge> edges;
vector<ll> prefix;
ll bestCover = 0;

void dfs(int pos, int taken, ll curSum) {
    if (taken == K) {
        bestCover = max(bestCover, curSum);
        return;
    }
    int rem = K - taken;
    if (pos + rem > (int)edges.size()) return;
    // upper bound: sum of next rem weights
    ll ub = curSum + (prefix[pos + rem] - prefix[pos]);
    if (ub <= bestCover) return;

    // try take edges[pos]
    const auto &e = edges[pos];
    if (!used[e.u] && !used[e.v]) {
        used[e.u] = used[e.v] = 1;
        dfs(pos + 1, taken + 1, curSum + e.w);
        used[e.u] = used[e.v] = 0;
    }
    // try skip
    dfs(pos + 1, taken, curSum);
}

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

    cin >> N >> K;
    vector<vector<int>> A(N, vector<int>(N));
    ll total = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> A[i][j];
            total += A[i][j];
        }
    }

    // build edge list
    edges.reserve(2LL * N * (N - 1));
    auto idx = [&](int i,int j){ return i * N + j; };
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if (i+1 < N) {
                edges.push_back({ idx(i,j), idx(i+1,j), A[i][j] + A[i+1][j] });
            }
            if (j+1 < N) {
                edges.push_back({ idx(i,j), idx(i,j+1), A[i][j] + A[i][j+1] });
            }
        }
    }

    // sort by weight descending
    sort(edges.begin(), edges.end(),
         [](auto &a, auto &b){ return a.w > b.w; });

    // cap to top L edges for search
    const int L = min<int>(edges.size(), 2000);
    edges.resize(L);

    // prefix sums of weights
    prefix.assign(L+1, 0);
    for(int i = 0; i < L; i++){
        prefix[i+1] = prefix[i] + edges[i].w;
    }

    // greedy initial solution to seed bestCover
    used.assign(N * N, 0);
    int got = 0;
    ll greed = 0;
    for(auto &e : edges){
        if (got == K) break;
        if (!used[e.u] && !used[e.v]) {
            used[e.u] = used[e.v] = 1;
            greed += e.w;
            got++;
        }
    }
    bestCover = (got == K ? greed : 0);
    // clear usage for exact search
    fill(used.begin(), used.end(), 0);

    // branch‐and‐bound search
    dfs(0, 0, 0LL);

    // answer = total sum – max covered
    cout << (total - bestCover) << "\n";
    return 0;
}

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