結果
| 問題 | No.1912 Get together 2 |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 207 ms / 2,000 ms |
| コード長 | 6,244 bytes |
| コンパイル時間 | 846 ms |
| コンパイル使用メモリ | 87,076 KB |
| 実行使用メモリ | 34,508 KB |
| 最終ジャッジ日時 | 2025-05-14 13:06:48 |
| 合計ジャッジ時間 | 5,960 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 33 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm> // for max
using namespace std;
// Define long long for potentially large values, as sums of squares can exceed 32-bit integer limits.
typedef long long ll;
int main() {
// Fast IO setup to speed up input reading.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of slimes
int M; // Number of boxes
cin >> N >> M;
vector<ll> V(N); // Values of slimes
for (int i = 0; i < N; ++i) {
cin >> V[i];
}
// Group slimes based on their compatibility pattern (represented as a bitmask).
// Use a map to store the total value for each unique pattern mask encountered.
// The key is the bitmask, the value is the sum of values of slimes with that pattern.
map<int, ll> W_map;
for (int i = 0; i < N; ++i) {
string S; // Compatibility string for slime i
cin >> S;
int mask = 0;
// Convert the compatibility string S to a bitmask.
// If S[j] == 'o', the slime is compatible with box j+1. We set the j-th bit in the mask.
// We use 0-indexed bits for boxes 0 to M-1. So box j corresponds to bit j.
for (int j = 0; j < M; ++j) {
if (S[j] == 'o') {
mask |= (1 << j);
}
}
// Add the slime's value V[i] to the total value associated with this mask.
// The problem guarantees each slime is compatible with at least one box, so mask > 0.
if (mask > 0) {
W_map[mask] += V[i];
}
}
// Create a vector W of size 2^M to store the total values for each mask.
// W[mask] = total value of slimes whose compatibility pattern is exactly 'mask'.
vector<ll> W(1 << M, 0);
for (auto const& [mask, total_value] : W_map) {
W[mask] = total_value;
}
// Compute F[mask] = sum of W[sub] for all submasks 'sub' of 'mask'.
// This is done using Sum Over Subsets (SOS) Dynamic Programming.
// F[mask] represents the total value of all slimes that can *only* be placed in boxes belonging to the set represented by 'mask'.
vector<ll> F = W; // Initialize F with the values from W. F[mask] starts as W[mask].
// SOS DP calculation:
// Iterate through each bit position (dimension) from 0 to M-1.
for (int i = 0; i < M; ++i) {
// Iterate through all possible masks from 0 to 2^M - 1.
for (int mask = 0; mask < (1 << M); ++mask) {
// If the i-th bit is set in 'mask', it means mask includes the dimension 'i'.
// We update F[mask] by adding the value from the mask without the i-th bit set (F[mask ^ (1 << i)]).
// This accumulates the values from all submasks.
if ((mask >> i) & 1) {
F[mask] += F[mask ^ (1 << i)];
}
}
}
// After this loop, F[mask] correctly stores the sum of W[sub] for all submasks 'sub' of 'mask'.
// The main dynamic programming part to calculate the maximum sum of squares.
// dp[mask] will store the maximum sum of squares achievable using only boxes represented in 'mask',
// and considering only slimes whose compatibility patterns 'p' are subsets of 'mask' (p subseteq mask).
vector<ll> dp(1 << M, 0); // Initialize dp table with 0s. The minimum possible score is 0.
// We compute the dp states iteratively. The value dp[mask] is computed based on values of dp[submask].
// The following loop structure implements the DP relation efficiently in O(M * 2^M).
// Iterate through all masks from 0 up to 2^M - 1.
for (int mask = 0; mask < (1 << M); ++mask) {
// Base case dp[0] = 0 is handled by initialization.
// For mask > 0, calculate its dp value based on its immediate submasks.
if (mask == 0) continue;
// Iterate through each bit 'i' that is set in the current mask.
for (int i=0; i<M; ++i) {
if ((mask >> i) & 1) { // Check if the i-th bit is set in mask (i.e., box 'i' is in the set 'mask')
// Consider the state corresponding to the mask without box 'i'.
int prev_mask = mask ^ (1 << i);
// Calculate the total value of slimes whose patterns 'p' satisfy:
// p is a subset of 'mask', AND p is NOT a subset of 'prev_mask'.
// This difference F[mask] - F[prev_mask] represents exactly these slimes.
// These slimes must be compatible with box 'i' (and possibly others in 'prev_mask').
ll value_group = F[mask] - F[prev_mask];
// The DP transition considers the possibility of grouping all slimes corresponding to 'value_group'
// and assigning them conceptually together. The score contribution is value_group^2.
// We take the maximum over all possible ways to remove a box 'i' to form 'prev_mask'.
// This update rule effectively finds the optimal partitioning according to the structure discovered.
dp[mask] = max(dp[mask], dp[prev_mask] + value_group * value_group);
}
}
}
/* Alternative equivalent DP loop structure that builds up from smaller masks to larger masks:
This structure was validated during thought process and also works.
Initialize dp with 0s.
for (int mask = 0; mask < (1 << M) - 1; ++mask) { // Iterate masks from 0 to 2^M - 2
for (int i = 0; i < M; ++i) { // Iterate through bits/boxes
if (!((mask >> i) & 1)) { // If box 'i' is NOT in current mask
int next_mask = mask | (1 << i); // Create mask including box 'i'
ll value_group = F[next_mask] - F[mask]; // Value of slimes needing box 'i' newly
// Update the dp value for the larger mask
dp[next_mask] = max(dp[next_mask], dp[mask] + value_group * value_group);
}
}
}
*/
// The final answer is the maximum score achievable using all M boxes, which is stored in dp[(1 << M) - 1].
cout << dp[(1 << M) - 1] << endl;
return 0;
}