Seen draw a big 3*n matrix , whose entries Ai,j are all integer numbers ( 1 <= i <= 3, 1 <= j <= n ). Now he selects k sub-matrices( each Aij only belong one sub-matrices ), hoping to find the largest sum of sub-matrices’ elements.

There are multiple test cases.

For each test case, the first line contains an integer n, k (1 <= n <= 100, 1 <= k <= 5, 3 * n >= k). The next three lines with n integers each gives the elements of the matrix ( | Ai,j | <= 10000).

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <vector>#include <queue>#include <map>#include <set>#include <stack>#include <algorithm>using namespace std;typedef long long LL;typedef pair<int,int> pii;const int mod = 1e9+7;const int N = 105 ;const int M = 13;#define X first#define Y secondint st1[M] = { 0 , 1 , 2 , 4 , 3 , 5 , 6 , 7 , 8 , 16 , 12 , 17 , 32 };int st2[M] = { 0 , 1 , 2 , 4 , 3 , 5 , 6 , 7 , 3 , 6 , 7 , 7 , 7 };int num[M] = { 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 1 , 1 , 2 , 2 , 1 };int A[3][N] , dp[N][6][M] , n , k ;int Sum( int colum , int st ) {    int res = 0 ;    for( int i = 0 ; i < 3 ; ++i ) if( st&(1<<i) )res += A[i][colum];    return res ;}void Run() {    memset( dp , 0x80 , sizeof dp ) ;    dp[0][0][0] = 0;    for( int i = 0 ; i < 3 ; ++i )        for( int j = 1 ; j <= n ; ++j )            cin >> A[i][j];    for( int i = 1 ; i <= n ; ++i ) {        for( int cs = 0 ; cs < M ; ++cs ) {            for( int ps = 0 ; ps < M ; ++ps ) {                int w = Sum(i,st2[cs]);                for( int k1 = 0 ; k1 <= k ; ++k1 ) {                    int low = num[cs] , up = num[cs] ;                    for( int z = 0 ; z < 6 ; ++z ) if( st1[cs] & st1[ps] &(1<<z) ) low--;                    for( int k2 = low ; k1 + k2 <= k && k2 <= up ; ++k2 ){                        dp[i][k1+k2][cs] = max( dp[i][k1+k2][cs] , dp[i-1][k1][ps] + w );                    }                }            }        }    }    cout << *max_element( dp[n][k] , dp[n][k]+M ) << endl ;}int main(){    #ifdef LOCAL        freopen("in.txt","r",stdin);    #endif // LOCAL    ios::sync_with_stdio(false);    while( cin >> n >> k )Run();}