Seletiva IOI 2014

inversor.cpp

// Ivan Carvalho
// Inversor - Seletiva IOI - OBI 2014
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 100010;
const ll NEG = -1*(1e13);
ll soma[MAXN],best[MAXN],resp;
int main(){
	ll N,K;
	resp = NEG;
	scanf("%lld %lld",&N,&K);
	for(ll i=1;i<=N;i++){
		scanf("%lld",&soma[i]);
		soma[i] = soma[i-1] - soma[i];
	}
	for(ll i=1;i<=N+1;i++) best[i] = NEG;
	ll fim = N; 
	ll ini = N - K + 1;
	while(ini >= 1){
		ll davez = soma[fim] - soma[ini-1];
		best[ini] = max(best[ini+1],davez);
		ini--;
		fim--;
	}
	ini = 1;
	fim = K;
	while(fim <= N){
		ll davez = soma[fim] - soma[ini-1];
		resp = max(resp,davez + best[fim+1]);
		ini++;
		fim++;
	}
	printf("%lld\n",resp);
	return 0;
}