Submission #1173067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173067		SUNWOOOOOOOO	Domino (COCI15_domino)	C++20	150 / 160	2430 ms	213732 KiB

domino

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pint = array <int, 2>;
using fint = array <int, 5>;
const int INF = 1e9;
int n, ntot, na, nb, k, ans = 0;
int dp[9][1 << 20], AisC[1 << 20], val[2001][2001], adj[51][51];
int vst[30];
LL sval = 0;
vector <fint> domino;
vector <int> A, B, curB;

void dfs(int mask, int sum){
    if (!curB.empty()){
        sum += B[curB.back()];
        for (int i = 0; i < na; i++){
            if (!adj[i][curB.back() + na] && (mask & (1 << i))) mask ^= (1 << i);
        }
    }
    ans = max(ans, sum + dp[k - (int) curB.size()][mask]);
    if ((int) curB.size() == k) return;
    if (curB.empty()){
        for (int i = 0; i < nb; i++){
            curB.push_back(i);
            dfs(mask, sum);
            curB.pop_back();
        }
    }
    else {
        for (int i = curB.back() + 1; i < nb; i++){
            int flag = 1;
            for (int elm : curB) if (!adj[i + na][elm + na]) flag = 0;
            if (flag){
                curB.push_back(i);
                dfs(mask, sum);
                curB.pop_back();
            }
        }
    }
}

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
        scanf("%d", &val[i][j]);
        sval += val[i][j];
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (i >= 2) domino.push_back({val[i][j] + val[i - 1][j], i, j, i - 1, j});
            if (j >= 2) domino.push_back({val[i][j] + val[i][j - 1], i, j, i, j - 1});
        }
    }
    sort(domino.begin(), domino.end());
    reverse(domino.begin(), domino.end());
    ntot = 7 * k - 6;
    na = min(20, ntot);
    nb = ntot - na;
    for (int i = 0; i < na; i++) A.push_back(domino[i][0]);
    for (int i = na; i < ntot; i++) B.push_back(domino[i][0]);
    for (int i = 0; i < ntot; i++){
        for (int j = 0; j < ntot; j++){
            if (i == j) continue;
            if ((pint) {domino[i][1], domino[i][2]} == (pint){domino[j][1], domino[j][2]} || 
            (pint){domino[i][1], domino[i][2]} == (pint){domino[j][3], domino[j][4]} ||
            (pint){domino[i][3], domino[i][4]} == (pint){domino[j][1], domino[j][2]} ||
            (pint){domino[i][3], domino[i][4]} == (pint){domino[j][3], domino[j][4]}) continue;
            adj[i][j] = 1;
        }
    }

    AisC[0] = 1;
    for (int mask = 0; mask < (1 << na); mask++){
        if (!AisC[mask]) continue;
        for (int i = 0; i < na; i++){
            if (mask & (1 << i)) continue;
            int flag = 1;
            for (int j = 0; j < na; j++) if ((mask & (1 << j)) && !adj[i][j]) flag = 0;
            if (flag) AisC[mask | (1 << i)] = 1;
        }
    }

    for (int d = 0; d <= k; d++){
        for (int mask = 0; mask < (1 << na); mask++) dp[d][mask] = -INF;
        for (int mask = 0; mask < (1 << na); mask++){
            if (__builtin_popcount(mask) == d && AisC[mask]){
                int sum = 0;
                for (int i = 0; i < na; i++) if (mask & (1 << i)) sum += A[i];
                dp[d][mask] = max(dp[d][mask], sum);
            }
            for (int i = 0; i < na; i++) dp[d][mask | (1 << i)] = max(dp[d][mask | (1 << i)], dp[d][mask]);
        }
    }

    dfs((1 << na) - 1, 0);

    printf("%lld\n", sval - ans);

    return 0;
}

Compilation message (stderr)

domino.cpp: In function 'int main()':
domino.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
domino.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d", &val[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

• 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: 0 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10
• Subtask 16: 10 / 10