C++14(g++5.4) 解法, 执行用时: 50ms, 内存消耗: 5072K, 提交时间: 2020-08-06 02:16:02

#include<bits/stdc++.h>
using namespace std;

long long R[200005],DP[200005],S[200005],INF=1e16;
int main()
{
    int i,n,t;
	scanf("%d%d",&n,&t);
    for(i=1;i<=n;i++)scanf("%lld",&R[i]);
    R[t]+=INF,S[1]=R[1];
    for(i=3;i<=n;i+=2)S[i]=S[i-2]+R[i];
    for(i=2;i<=n;i++)
    {
    	if(i&1)DP[i]=max(DP[i-1],DP[i-2]+R[i]);
    	else DP[i]=max(S[i-1],DP[i-2]+R[i]);
	}
    printf("%lld\n",DP[n]-INF);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 80ms, 内存消耗: 7240K, 提交时间: 2020-08-06 10:22:43

#include<bits/stdc++.h>
#define N 200005
using namespace std;
long long a[N],dp[N],s[N],p=1e16;
int main(){
	int n,x,i;cin>>n>>x;
	for(i=1;i<=n;i++)cin>>a[i];
	a[x]+=p;s[1]=a[1];
	for(i=3;i<=n;i+=2)s[i]=s[i-2]+a[i];
	for(i=2;i<=n;i++)
	if(i&1)dp[i]=max(dp[i-1],dp[i-2]+a[i]);
	else dp[i]=max(dp[i-2]+a[i],s[i-1]);
	cout<<dp[n]-p;
}