Given an enteger grid of dimensions $R \times C$ ($R \leq 12$, $C \leq 2000$), the optimization objective is to assign disjoint subsets of row indices to a selected group of columns. Each assigned column may undergo an independent vertical cyclic shift. The contribution of a column to its allocated rows equals the sum of the elements at those specifci positions. The final result should maximize the aggregate sum across all rows.

Constraints: Time limit $8\text{s}$, Memory limit $1\text{GB}$. Input format specifies $R$ and $C$, followed by the matrix elements where each value $a_{i,j} \leq 10^5$.

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX_ROWS = 13;
const int COL_CAPACITY = 114519;

struct Column {
    int values[MAX_ROWS];
    int peakVal;
    void reset() { peakVal = 0; }
    void updatePeak(int rCount) {
        peakVal = 0;
        for (int i = 0; i < rCount; ++i)
            peakVal = max(peakVal, values[i]);
    }
    bool operator<(const Column& other) const {
        return peakVal > other.peakVal;
    }
} matrixCols[COL_CAPACITY];

int memoState[MAX_ROWS][1 << MAX_ROWS];
int bestSubset[(1 << MAX_ROWS)];

inline void iterateSubmask(int &sub, int fullMask) {
    sub = (fullMask & (sub - 1));
}

int main() {
    int R, C;
    cin >> R >> C;
    
    memset(memoState, 0, sizeof(memoState));
    
    for (int j = 0; j < C; ++j) matrixCols[j].reset();
    
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
            cin >> matrixCols[c].values[r];
            
    for (int c = 0; c < C; ++c) matrixCols[c].updatePeak(R);
    sort(matrixCols, matrixCols + C);
    
    int pickLimit = min(R, C);
    
    for (int colIdx = 0; colIdx < pickLimit; ++colIdx) {
        for (int mask = 0; mask < (1 << R); ++mask) {
            bestSubset[mask] = 0;
            
            for (int shift = 0; shift < R; ++shift) {
                int currentSum = 0;
                for (int bit = 0; bit < R; ++bit) {
                    if ((mask >> bit) & 1)
                        currentSum += matrixCols[colIdx].values[(bit + shift) % R];
                }
                bestSubset[mask] = max(bestSubset[mask], currentSum);
            }
        }
        
        for (int mask = 0; mask < (1 << R); ++mask) {
            if (colIdx == 0) {
                memoState[colIdx][mask] = bestSubset[mask];
                continue;
            }
            
            memoState[colIdx][mask] = memoState[colIdx - 1][mask];
            int tempMask = mask;
            while (tempMask) {
                memoState[colIdx][mask] = max(
                    memoState[colIdx][mask],
                    memoState[colIdx - 1][tempMask] + bestSubset[tempMask ^ mask]
                );
                iterateSubmask(tempMask, mask);
            }
        }
    }
    
    cout << memoState[pickLimit - 1][(1 << R) - 1] << endl;
    return 0;
}

Assessment Module

True/False Questions:

1. (2') If iterateSubmask is rewritten as:

   inline void iterateSubmask(int &sub, int fullMask) {
       sub = fullMask & sub - 1;
   }
   

   The program will encounter a logical error.

2. (1.5') Replacing the output index memoState[pickLimit - 1][(1 << R) - 1] with memoState[R < C ? R : C - 1][(1 << R) - 1] will trigger a runtime failure.

3. (1.5') Increasing $C$ to $114514$ will cause this implementation to fail correctly handling the input constraints.

4. (2') The core operation supported by this algorithm is swapping two horizontal row sequences.

5. (2') The solver exclusively considers the top $R$ columns based on their maximum element.

Multiple Choice Questions:

1. (2') Which computational paradigm is primarily utilized? A. Bitmask DP B. Digit DP C. Primal-Dual Optimization D. Hash-based Mapping

2. (4') What is the asymptotic time complexity? A. $O(R^3 2^R + R 3^R + C \log C)$
   B. $O(R^3 2^R + R^2 3^R + RC \log R)$
   C. $O(R^2 C 2^R + R 3^R + C \log C)$
   D. $O(R^3 2^R + R^2 3^R + C \log R)$

3. (4') For the following test case, determine the output:

   3 6
   4 1 5 2 10 4
   8 6 6 4 9 10
   5 4 9 5 8 7
   

   A. 25 B. 27 C. 29 D. 33

4. (10') What does the recursive submask traversal sub = (mask & (sub - 1)) fundamentally represent in combinatorial optimizations? A. Lexicographical string sorting B. Iterating through all subsets of a bitmask C. Calculating GCD via Euclidean reduction D. Hash collision resolution