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
#include<bits/stdc++.h>
using namespace std;
const int N=205, K=65;
const long long INF=-1000000000000000000;
long long tab[N], sum[N][N], dp[K][N][N], f[K][N], dl[K];
int main(){
    int n;
    long long m;
    cin>>n>>m;
    for(int i=0; i<n ;i++){
        cin>>tab[i];
    }
    for(int i=0; i<n; i++){
        sum[i][i]=tab[i];
        f[0][i]=INF;
        for(int j=i+1; j<n; j++){
            sum[i][j]=sum[i][j-1]+tab[j];
        }
    }
    for(int l=1; ((long long)1<<l)<=(m+1); l++){
        long long pow=((long long)1<<l);
        //cout<<pow<<" ";
        //cout<<l<<" ";
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(j-i>=pow){
                    break;
                }
                dp[l][i][j]=INF;
                for(int k=max((long long)i-1, j-pow/2); k<=j and k<i+pow/2; k++){
                    dp[l][i][j]=max(dp[l][i][j], dp[l-1][i][k]+sum[k+1][j]+dp[l-1][k+1][j]);
                }
                //cout<<dp[l][i][j]<<" ";
            }
            //cout<<"\n";
        }
        //cout<<"\n";
    }
    bitset<64> t(m+1);
    int wsk=1;
    for(int i=63; i>=0; i--){
        if(t[i]){
            dl[wsk++]=i;
        }
    }
    //cout<<dl[1]<<dl[2]<<wsk<<" ";
    long long suma=0;
    for(int k=1; k<wsk; k++){
        suma+=((long long)1<<dl[k]);
        long long pow=((long long)1<<dl[k]);
        for(int i=0; i<n and i<suma ; i++){
            f[k][i]=dp[dl[k]][0][i];

            for(int j=max((long long)0, i-pow); j<=i; j++){
                f[k][i]=max(f[k][i], f[k-1][j]+(k-1)*sum[j+1][i]+dp[dl[k]][j+1][i]);
            }
            //cout<<f[k][i]<<" ";
        }
        //cout<<"\n";
    }
    //cout<<suma;
    cout<<f[wsk-1][n-1];
}