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
#include <iostream>
#include <math.h>
#include <vector>

int N, M;

std::vector<long long int> BITES;
std::vector<long long int> SCORE[2];

int main() {
    std::ios::sync_with_stdio(false);

    std::cin >> N >> M;

    BITES = std::vector<long long int>(M + 12, 0);
    SCORE[0] = std::vector<long long int>(M + 12, 0);
    SCORE[1] = std::vector<long long int>(M + 12, 0);

    for (int i = 1; i <= M; i ++ )
        BITES[i] = BITES[i / 2] + i % 2;

    for (int i = 1; i <= N; i ++ ) {
        long long int note;
        std::cin >> note;

        if (i > 1)
            SCORE[i % 2][i - 1] = SCORE[(i - 1) % 2][i - 2] + BITES[i - 1] * note;

        for (int j = i; j <= M; j ++) {
            SCORE[i % 2][j] = std::max(SCORE[i % 2][j - 1], SCORE[(i - 1) % 2][j - 1] + BITES[j] * note);
        }
    }

    std::cout << SCORE[N % 2][M] << std::endl;
}