結果
| 問題 |
No.1345 Beautiful BINGO
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,010 bytes |
| コンパイル時間 | 1,110 ms |
| コンパイル使用メモリ | 102,816 KB |
| 実行使用メモリ | 19,712 KB |
| 最終ジャッジ日時 | 2025-05-14 13:17:06 |
| 合計ジャッジ時間 | 5,446 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 TLE * 1 -- * 39 |
ソースコード
#include <iostream>
#include <vector>
#include <bitset>
#include <map> // Include map if using standard map for caching
#include <unordered_map> // Include unordered_map for potentially faster caching
#include <algorithm>
#include <limits> // For numeric_limits to initialize minimum cost
using namespace std;
// Define compile-time constants based on the maximum possible N (N=16)
// This is necessary because std::bitset requires a compile-time size.
const int MAXN_COMPILE = 16;
// Maximum number of cells in the grid (N*N)
const int MAX_CELLS_COMPILE = MAXN_COMPILE * MAXN_COMPILE; // 16*16 = 256
// Maximum number of lines (N rows + N columns + 2 diagonals)
const int MAX_LINES_COMPILE = 2 * MAXN_COMPILE + 2; // 2*16 + 2 = 34
// Global variables
long long A[MAXN_COMPILE][MAXN_COMPILE]; // Store the input cost matrix
long long cell_costs[MAX_CELLS_COMPILE]; // Flattened 1D array for cell costs for easier access by index
int N; // Actual grid size from input (will be <= MAXN_COMPILE)
int N_squared; // Cached value of N*N
// Array of bitsets, where each bitset represents the set of cells belonging to a line
bitset<MAX_CELLS_COMPILE> line_masks[MAX_LINES_COMPILE];
// Cache to store computed costs for cell sets (bitsets). Using unordered_map for potentially better performance.
// Key: bitset representing a subset of cells. Value: total cost for opening these cells.
unordered_map<bitset<MAX_CELLS_COMPILE>, long long> cost_cache;
// Function to compute the total cost for opening a given set of cells S, represented by a bitset.
// Uses caching to avoid recomputing costs for the same set of cells.
long long compute_cost(const bitset<MAX_CELLS_COMPILE>& S) {
// Check if the cost for this bitset S is already in the cache
auto cache_it = cost_cache.find(S);
if (cache_it != cost_cache.end()) {
// If found, return the cached cost
return cache_it->second;
}
long long current_cost = 0;
// Iterate through all possible cell indices (0 to N*N - 1)
for (int k = 0; k < N_squared; ++k) {
// If the k-th bit is set in S, it means cell k is included in the set
if (S.test(k)) {
// Add the cost of cell k to the total cost
current_cost += cell_costs[k];
}
}
// Store the newly computed cost in the cache before returning
cost_cache[S] = current_cost;
return current_cost;
}
int main() {
// Use fast I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int M; // Required minimum number of completed lines
cin >> N >> M; // Read grid size N and minimum lines M
N_squared = N * N; // Cache N*N
// Read the cost matrix A and populate the flattened cell_costs array
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> A[i][j];
// Map 2D index (i, j) to 1D index k = i*N + j
cell_costs[i * N + j] = A[i][j];
}
}
int line_idx = 0; // Initialize index for the line_masks array
// Precompute bitmasks representing the cells for each row
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
line_masks[line_idx].set(i * N + j); // Set the bit corresponding to cell (i, j)
}
line_idx++; // Move to the next line index
}
// Precompute bitmasks for each column
for (int j = 0; j < N; ++j) {
for (int i = 0; i < N; ++i) {
line_masks[line_idx].set(i * N + j); // Set the bit for cell (i, j)
}
line_idx++;
}
// Precompute bitmask for the Main Diagonal (top-left to bottom-right)
for (int i = 0; i < N; ++i) {
line_masks[line_idx].set(i * N + i); // Set the bit for cell (i, i)
}
line_idx++;
// Precompute bitmask for the Anti-Diagonal (top-right to bottom-left)
for (int i = 0; i < N; ++i) {
// The cell is (i, N-1-i)
line_masks[line_idx].set(i * N + (N - 1 - i));
}
line_idx++;
int total_lines = line_idx; // The total number of lines is 2N+2
// Divide the lines into two halves for the meet-in-the-middle approach
int num_lines_A = total_lines / 2;
int num_lines_B = total_lines - num_lines_A;
// --- Meet-in-the-Middle Part 1: Generate states for the first half of lines ---
vector<pair<bitset<MAX_CELLS_COMPILE>, int>> list_A; // Stores pairs of (cell_mask, line_count)
int limit_A = 1 << num_lines_A; // Total number of subsets for the first half = 2^(num_lines_A)
list_A.reserve(limit_A); // Reserve memory to potentially speed up vector insertions
// Iterate through all possible subsets of the first half lines using bitmask 'i'
for (int i = 0; i < limit_A; ++i) {
bitset<MAX_CELLS_COMPILE> current_S_A; // Stores the union of cells for the current subset of lines
int current_k_A = 0; // Counts the number of lines in the current subset
// Check each line in the first half
for (int j = 0; j < num_lines_A; ++j) {
// If the j-th bit of 'i' is set, it means the j-th line is included in this subset
if ((i >> j) & 1) {
current_k_A++; // Increment line count
current_S_A |= line_masks[j]; // Union the cells of this line into the combined mask
}
}
// Store the generated cell mask and the number of lines completed
list_A.push_back({current_S_A, current_k_A});
}
// --- Meet-in-the-Middle Part 2: Generate states for the second half of lines ---
vector<pair<bitset<MAX_CELLS_COMPILE>, int>> list_B; // Stores pairs of (cell_mask, line_count)
int limit_B = 1 << num_lines_B; // Total number of subsets for the second half = 2^(num_lines_B)
list_B.reserve(limit_B); // Reserve memory
// Iterate through all possible subsets of the second half lines using bitmask 'i'
for (int i = 0; i < limit_B; ++i) {
bitset<MAX_CELLS_COMPILE> current_S_B; // Combined cell mask
int current_k_B = 0; // Line count
// Check each line in the second half
for (int j = 0; j < num_lines_B; ++j) {
// If the j-th bit of 'i' is set, include this line
if ((i >> j) & 1) {
current_k_B++;
// The lines in the second half start at index num_lines_A in the line_masks array
current_S_B |= line_masks[num_lines_A + j]; // Union cells
}
}
// Store the generated mask and line count
list_B.push_back({current_S_B, current_k_B});
}
// --- Combine results from both halves ---
// Initialize minimum total cost to the maximum possible value for a long long
long long min_total_cost = numeric_limits<long long>::max();
// Iterate through all pairs of states (one from list_A, one from list_B)
for (const auto& pA : list_A) {
const bitset<MAX_CELLS_COMPILE>& S_A = pA.first; // Cell mask from the first half state
int k_A = pA.second; // Line count from the first half state
for (const auto& pB : list_B) {
const bitset<MAX_CELLS_COMPILE>& S_B = pB.first; // Cell mask from the second half state
int k_B = pB.second; // Line count from the second half state
// Check if the total number of completed lines (k_A + k_B) meets the requirement M
if (k_A + k_B >= M) {
// Calculate the union of cells required by both halves using bitwise OR
bitset<MAX_CELLS_COMPILE> S_union = S_A | S_B;
// Compute the cost for this combined set of cells (using the cache)
long long current_total_cost = compute_cost(S_union);
// Update the overall minimum cost if the current combination is cheaper
min_total_cost = min(min_total_cost, current_total_cost);
}
}
}
// Output the minimum total cost found
cout << min_total_cost << endl;
return 0;
}