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
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define st first
#define nd second
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define Q 1000000007
#define inf 1300000000000000003
#define maxn 203

int n, logm=-1;
ll m;
ll dp[63][maxn][maxn], dp2[64][maxn][maxn];
ll pot[63], sum[maxn][maxn];
ll A[maxn];

void ini(){
    scanf("%d%lld", &n, &m);
    for(int i=1; i<=n; i++) scanf("%lld", &A[i]);
    m++;
    ll y=1;
    pot[0]=1;
    for(int i=1; i<=60; i++){
        y*=2;
        if(y>=m && logm==-1){
            logm=i;
        }
        pot[i]=y;
    }

    for(int i=1; i<=n; i++){
        ll s=0;
        for(int j=i; j<=n; j++){
            s+=A[j];
            sum[i][j]=s;
        }
    }
}

void calc_dp(){
    for(int i=0; i<=logm; i++){
        for(int j=1; j<=n; j++){
            for(int z=j; z<=n; z++){
                dp[i][j][z]=-inf;
                dp2[i][j][z]=-inf;
            }
        }
    }
    for(int i=1; i<=n; i++){
        dp[0][i][i]=0;
    }
    for(int h=1; h<=logm; h++){
        for(int a=1; a<=n; a++){
            for(int b=a; b<=n && b-a+1<=pot[h]; b++){
                for(int k=a-1; k<=b; k++){
                    dp[h][a][b]=max(dp[h][a][b], dp[h-1][a][k]+dp[h-1][k+1][b]+sum[k+1][b]);
                }
            }   
        }
    }
}

void solve(){
    ll w=m+pot[logm]-1;
    int h=1;
    ll l=m, r=m;
    for(int i=1; i<=n; i++){
        dp2[0][i][i]=0;
    }
    while(w>1){
        if(w%2==1){
            l-=(r-l+1);
        }
        else r+=(r-l+1);
        for(int a=1; a<=n; a++){
            for(int b=a; b<=n && b-a+1<=m-l+1; b++){
                if(w%2==1){
                    for(int k=a-1; k<=b; k++){
                        dp2[h][a][b]=max(dp2[h][a][b], dp[h-1][a][k]+dp2[h-1][k+1][b]+sum[k+1][b]);
                    }
                }
                else{
                    dp2[h][a][b]=max(dp2[h][a][b], dp2[h-1][a][b]);
                }
            }   
        }
        w/=2;
        h++;
    }
}

int main(){
    ini();
    calc_dp();
    solve();
    ll odp=dp2[logm][1][n];
    printf("%lld\n", odp);
}