Решение задачи Игра с монетами с Меньшиков

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
#define USE_VECTOR
 
#ifdef USE_VECTOR
vector<vector<int> > keep; // keep[k][n] - сколько монет получишь если K = k и осталось n стопок
vector<vector<int> >leave; // leave[k][n] - сколько монет оставишь, если сделаешь ход keep[k][n]
#else
int keep[85][185], leave[85][185];
#endif
 
int n,k;
vector<int> mas,sums;
 
void input()
{
    cin>>n;
    mas.resize(n);
    sums.resize(n);
    for (int i=0;i<n;i++)
    {
        cin>>mas[i];
        sums[i] = mas[i];
        if (i!=0)
            sums[i] += sums[i-1];
           
    }
    cin>>k;
 
#ifdef USE_VECTOR
    keep = vector<vector<int> >(k, vector<int>(n+1,0));
    leave = vector<vector<int> >(k, vector<int>(n+1,0));
#endif
}
 
// быстрый подсчет суммы элементов в интервале [f,s]
inline int sum(int f, int s)
{
    return sums[s] - sums[f] + mas[f];
}
void solve()
{
    // заполняем первую строчку в обоих матрицах
    // используя принцип чередования ходов
    keep[0][n-1] = mas[n-1];
    for (int j = n-2; j>=0;j--)
    {
        keep[0][j]  = keep[0][j+2] + mas[j];
        leave[0][j] = keep[0][j+1];
    }
 
    for (int i = 1; i < k; i++)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            // находим наилучший ход сверху,
            // т.е находим наилучший ход, если будем уменьшать K
            int MaxUpKeep = 0;
            int posUp = 0;
            for (int p = i - 1; p >= 0; p--)
            {
                if (MaxUpKeep < keep[p][j])
                {
                    MaxUpKeep = keep[p][j];
                    posUp = p;
                }
            }
            // находим наилучший ход справа,
            // т.е. оставляем K без изменений
            int last = min(j + i, n-1);
            int MaxRightKeep = sum(j,last) + leave[i][last+1];
 
            if (MaxUpKeep > MaxRightKeep)
            {
                keep[i][j]  = keep[posUp][j];
                leave[i][j] = leave[posUp][j] ;
            }
            else
            {
                keep[i][j]  = MaxRightKeep;
                leave[i][j] = keep[i][last+1];
            }
        }
    }
}
void output()
{
    cout<<keep[k-1][0];
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    output();
    return 0;
}