INOI 2013 Calvins Game solution.

#include<bits/stdc++.h>
using namespace std;
#define s(x) scanf("%lld",&x)
int n;
long long a[1000001]={0};
long long dp[1000001][2];
#define mini INT_MIN
long long rec(int i,bool phase){
    if(dp[i][phase]==-1){
    long long x,y,p=-mini,q=-mini;
    if(i>2){
        x=rec(i-1,0)+a[i-1];
        y=rec(i-2,0)+a[i-2];
    }
    else if(i>1){
        x=rec(i-1,0)+a[i-1];
        y=-mini;
    }
    else{
         x=0;
         y=0;
    }
    if(phase){
        if(i<n-1){
            p=rec(i+1,1)+a[i+1];
            q=rec(i+2,1)+a[i+2];
        }
        else if(i<n){
            p=rec(i+1,1)+a[i+1];
        }
    }
    dp[i][phase]= max(max(p,q),max(x,y));
    }
    return dp[i][phase];
   
}
int main(){
    int k;
    s(n);
    s(k);
    for(int i=1;i<=n;i++){
        s(a[i]);
    }
    memset(dp,-1,sizeof(dp));
    printf("%lld",rec(k,1));
}