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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdint>
#include <cstdio>
#include <cstdlib>

#include <algorithm>
#include <array>
#include <numeric>

// #define SHOWDEBUG

const uint64_t MAX_N = 200;
const uint64_t MAX_LOG_M = 63;

using arr_t = std::array<std::array<std::array<int64_t, MAX_N + 1>, MAX_N + 1>,
                         MAX_LOG_M>;

std::array<int64_t, MAX_N + 1> prefix_sum = {};
arr_t best_normal = {};
arr_t best_overhang = {};

inline void compute_slice(arr_t& left_arr,
                          uint64_t left_level,
                          arr_t& right_arr,
                          uint64_t right_level,
                          uint64_t right_size,
                          arr_t& target_arr,
                          uint64_t target_level,
                          unsigned int n) {
  const uint64_t powlevel_left = (uint64_t)1 << left_level;
  const auto max_width_left = std::min(powlevel_left, (uint64_t)n);
  const auto max_width_right = std::min(right_size, (uint64_t)n);

  const auto max_width_target = max_width_left + max_width_right;

#ifdef SHOWDEBUG
  printf("Levels (%lu, %lu, %lu)\n", left_level, right_level, target_level);
#endif

  // Iterate over each pair
  for (uint64_t begin = 0; begin < n; begin++) {
    const auto limit = std::min(begin + max_width_target, (uint64_t)n);
    for (uint64_t end = begin + 1; end <= limit; end++) {
      auto local_best = std::numeric_limits<int64_t>::min();
      auto begin_offset =
          (end - begin) - std::min(end - begin, max_width_right);
      auto end_offset = (end - begin) - std::min(end - begin, max_width_left);

#ifdef SHOWDEBUG
      printf(" Iterating over [%lu, [%lu, %lu), %lu)\n", begin,
             begin + begin_offset, end - end_offset, end);
#endif

      for (uint64_t pivot = begin + begin_offset; pivot <= end - end_offset;
           pivot++) {
        const auto candidate = left_arr[left_level][begin][pivot] +
                               (prefix_sum[end] - prefix_sum[pivot]) +
                               right_arr[right_level][pivot][end];
        local_best = std::max(local_best, candidate);
#ifdef SHOWDEBUG
        printf("   Candidate [%lu, %lu, %lu) = %ld\n", begin, pivot, end,
               candidate);
#endif
      }

      target_arr[target_level][begin][end] = local_best;

#ifdef SHOWDEBUG
      printf("  Result [%lu, %lu) = %lld\n", begin, end,
             (long long int)target_arr[target_level][begin][end]);
#endif
    }
  }
}

int main() {
  unsigned int n;
  unsigned long long int lld_m;
  (void)scanf("%u %lld", &n, &lld_m);

  const uint64_t m = (uint64_t)lld_m;

  // Load input and store as prefix sum
  prefix_sum[0] = 0;
  int64_t accum = 0;
  for (uint64_t i = 1; i <= n; i++) {
    long long int x;
    (void)scanf("%lld", &x);
    accum += (int64_t)x;
    prefix_sum[i] = accum;
  }

  auto shlevel = [](uint64_t level) -> uint64_t {
    return (uint64_t)1 << (uint64_t)level;
  };

  // Compute one table
#ifdef SHOWDEBUG
  puts("--- COMPUTE ONE ---");
#endif
  for (int level = 1; shlevel(level) <= m; level++) {
    compute_slice(best_normal, level - 1, best_normal, level - 1,
                  shlevel(level - 1), best_normal, level, n);
  }

  // Compute second table
#ifdef SHOWDEBUG
  puts("--- COMPUTE SECOND ---");
#endif
  uint64_t source_level = 0;
  uint64_t target_level = 0;
  uint64_t right_size = 1;
  while (shlevel(target_level) <= m) {
    if ((shlevel(target_level) & m) == 0) {
      target_level++;
      continue;
    }

    target_level++;

    compute_slice(best_normal, target_level - 1, best_overhang, source_level,
                  right_size, best_overhang, target_level, n);

    source_level = target_level;
    right_size += shlevel(target_level - 1);
  }

  // Compute combined
#ifdef SHOWDEBUG
  puts("--- COMPUTE COMBINED ---");
#endif

  const auto result = best_overhang[target_level][0][n];
  printf("%lld\n", (long long int)result);

  return 0;
}