Cherchez vol 2 - Tren - pag 178 - 95 puncte

#include <bits/stdc++.h>
// http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=510

using namespace std;

ifstream fin("tren1.in");
ofstream fout("tren1.out");

const int NMAX = 5e4 + 5;
int a[NMAX], sum[NMAX], dp[NMAX][4];

int main() {
    int N;
    fin >> N;
    for(int i = 1; i <= N; ++i) {
        fin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    int M;
    fin >> M;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= 3; ++j)
            dp[i][j] = sum[i];
    for(int i = M + 1; i <= N; ++i)
        for(int j = 1; j <= 3; ++j)
            dp[i][j] = max(dp[i - 1][j], sum[i] - sum[i - M] + dp[i - M][j - 1]);
    fout << dp[N][3];
}