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
#include <iostream>
#include <unordered_map>
#include <algorithm>

#define I long long
#define MAX 220
#define INF 2280000000000000000LL

I a[MAX], s[MAX], n, m;
#define D(x)

struct F {
    I v[MAX][MAX];
    void init(int x = 0) {
        for(int i=0;i<=n;i++)
            for(int j=0;j<=n;j++) v[i][j] = -INF*2;
        for(int i=0;i<=n;i++) v[i][i] = 0;
        if(x == 1) for(int i=0;i<=n;i++) v[i][i+1] = 0;
    }
    void print() {
        for(int i=0;i<=n;i++) {
            for(int j=0;j<=n;j++) {
                std::cout << v[i][j] << " ";
            }
            std::cout << "\n";
        }
    }
};

F combile(const F& a, const F& b) {
    F r;
    r.init();
    for(int i=0;i<=n;i++) {
        for(int j=i;j<=n;j++) {
            I res = -2*INF;
            for(int t=i;t<=j;t++) {
                res = std::max(res, a.v[i][t] + b.v[t][j] + s[j]-s[t]);
            }
            if (res < -INF) res = -2*INF;
            r.v[i][j] = res;
        }
    }
    return r;
}

I f(int i, int j, I m, int d = 0) {
    if(i==j) return 0;
    if(i>j || m+i<j) {
   //     std::cout << i << " " << j << " (0," << m << ") " << s << " = INF\n";
        return -INF;
    }
    if(m == 1 && j-i == 1) {
        D(std::cout << std::string(d*3, ' ') << i << " " << j << " (0," << m << ") " << s << " = " << 0 << "\n");
        return 0;
    }
    I res = -INF;
    I v = 1;
    while(v<m) v*=2;
    v/=2;
    int idx = 0;
 //   std::cout << i << " " << j << " v = " << v << "\n";
    for(int t=i;t<=j;t++) {
        D(std::cout << std::string((d+1)*3, ' ') << i << " " << t << " " << j <<  " m,v="  << m << "," << v << "\n");
        I r1 = f(i,t,v,d+1) + f(t,j,m-v,d+1) + s[j]-s[t];
        if(r1>res) {
            res = r1;
            idx = t;
        }
    }
    D(std::cout << std::string(d*3, ' ') << i << " " << j << " (0," << m << ") " << s << " = " << res << " (" << idx << ")\n");
    return res;
}



int main()
{
    std::cin >> n >> m;
    for(I i=0;i<n;i++) std::cin >> a[i];
    for(I i=0;i<n;i++) s[i+1] = s[i] + a[i];

    F pf, w;
    w.init();
    pf.init(1);
    I pi = 1, mm = m+1;
    while(mm) {
        if(mm&pi) {
            w = combile(pf, w);
            mm -= pi;
        }
        D(std::cout << pi << "\n";
        pf.print());
        pi+=pi;
        pf = combile(pf, pf);
    }
    std::cout << w.v[0][n] << "\n";

    D(
    for(int i=0;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            std::cout << f(i,j,4) << " ";
        }
        std::cout << "\n";
    }


    std::cout << f(0,n,m+1) << "\n";
    );
}