Submission #1173061

#TimeUsernameProblemLanguageResultExecution timeMemory
1173061SUNWOOOOOOOODomino (COCI15_domino)C++20
150 / 160
3277 ms213720 KiB
#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 = (1 << na) - 1, sum = 0; for (int elm : curB){ sum += B[elm]; for (int i = 0; i < na; i++){ if (!adj[i][elm + 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(); 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(); 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(); printf("%lld\n", sval - ans); return 0; }

Compilation message (stderr)

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