1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define lld long long

const lld N=203;
const lld L=48;
const lld inf=-1e18-5;

bool quick=false;

lld ile=0;
lld n, m, p;
lld a[N];
lld pref[N];
lld dp[N][N][L];
lld jedynka[L];
lld suff[N][L];

lld sum(int a, int b){
    if(a>b) return -1;
    else return pref[b]-pref[a-1];
}

lld check(){
    lld k=1;
    lld ile=1;
    while(k<m){
        ile++;
        k*=2;
    }
    if(k-1==m) quick=true; //xddd
    return ile-1;
}

void count2(lld i, lld k){
    suff[i][k]=suff[i][k-1];
    for(int j=n; j>=i; j--){
        if(dp[j][n][jedynka[k]]!=inf)
            suff[i][k]=max(suff[i][k], k*sum(j, n)+dp[j][n][jedynka[k]]+suff[i][k-1]-suff[j][k-1]);
    }
}

void solve2(){
    for(int k=1; k<=ile; k++){
        for(int i=n; i>0; i--){
            count2(i, k);
        }
    }
}

void jazda(){
    ile=0;
    for(int i=0; i<p; i++){
        if(m&(1<<i)) ile++;
    }
    int l=ile;
    for(int i=0; i<p; i++){
        if(m&(1<<i)){
            jedynka[l]=i;
            l--;
        }
    }
    for(int i=n; i>0; i--){
        suff[i][0]=dp[i][n][p];
    }
    solve2();
    cout<<suff[1][ile]<<"\n";
}


void count(lld i, lld j, lld k){
    dp[i][j][k]=dp[i][j][k-1];
    if(dp[i][j][k]!=inf) dp[i][j][k]=max(dp[i][j][k], dp[i][j][k]+sum(i, j));

    for(int x=1; x<j-i+1; x++){
        if(dp[i][i+x-1][k-1]!=inf && dp[i+x][j][k-1]!=inf)
            dp[i][j][k]=max(dp[i][j][k], dp[i][i+x-1][k-1]+dp[i+x][j][k-1]+sum(i+x, j));
    }
}

void solve(){
    for(lld k=1; k<=p; k++){
    	for(lld l=1; l<=n; l++){
    		for(lld i=1; i+l-1<=n; i++){
    			lld j=i+l-1;
    			count(i, j, k);
                //cout<<dp[i][j][k] <<" "<<i<<" "<<j<<" "<<k<<endl;
    		}
    	}
    }
}

int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        pref[i]=pref[i-1]+a[i];
    }
    p=check();
    //cout<<p<<endl;
    for(int i=1; i<=n; i++){ //inty
        for(int j=1; j<=n; j++){
            for(int k=0; k<=p; k++){
                dp[i][j][k]=inf;
            }
        }
    }
    for(int i=1; i<=n; i++){
        dp[i][i][0]=0;
    }
    solve();
    if(quick) cout<<dp[1][n][p]<<"\n";
    else jazda();
}