【Educational Codeforces Round 48 (Rated for Div. 2) C】 Vasya And The Mushrooms

在这里输入题意

【题解】

显然在没有一直往右走然后走到头再往上走一格再往左走到头之前。肯定是一直在蛇形走位。。这个蛇形走位的答案贡献可以预处理出来。很容易。然后蛇形走位之后走到最右再掉头的这个过程也能倒推出来。考虑sum[i]和sum[i+1]的转移就好显然sum[i]只是多了a[i]和b[i]两个格子。考虑它们的贡献就好。 sum[i]表示从i开始一直走到右,然后再走到左的花费。(且i位置作为t=0 (之后只要把i后面的和乘上之前过的时间elapsed+sum[i],那么就变成t=elapsed开始的啦但是往右走有两种可能。一种是从a[i]开始。另外一种是从b[i]开始。所以sum得开成两维的。枚举一下从哪里开始,之后一直往右走再一直往左走就可以了。注意爆int的问题。

【代码】

#include <bits/stdc++.h>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define lson l,mid,rt<<1
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x)
#define rson mid+1,r,rt<<1|1
using namespace std;

const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
const int N = 3e5;

int n;
int a[2][N+10];
LL right_to_left[2][N+10],sum2[N+10],cur,ans;

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "r", stdin);
	#endif
	ri(n);
    rep1(i,0,1)
        rep1(j,1,n)
            ri(a[i][j]);
    rep2(i,n,1){
        sum2[i] = sum2[i+1]+a[0][i]+a[1][i];
    }
    rep2(i,n,1){
        right_to_left[0][i] = right_to_left[0][i+1] + sum2[i+1] + 0*a[0][i] + 1LL*((n-i+1)*2-1)*a[1][i];
        right_to_left[1][i] = right_to_left[1][i+1] + sum2[i+1] + 0*a[1][i] + 1LL*((n-i+1)*2-1)*a[0][i];
    }
    cur = 0;
    ans = right_to_left[0][1];
    rep1(i,1,n){
        if (i&1){
            LL time_elapsed = (i-1)*2;
            cur+=time_elapsed*a[0][i];
            time_elapsed++;
            cur+=time_elapsed*a[1][i];
            ans = max(ans,1LL*(cur+(time_elapsed+1)*sum2[i+1]+right_to_left[1][i+1]));
        }else{
            LL time_elapsed = (i-1)*2;
            cur+=time_elapsed*a[1][i];
            time_elapsed++;
            cur+=time_elapsed*a[0][i];
            ans = max(ans,1LL*(cur+(time_elapsed+1)*sum2[i+1]+right_to_left[0][i+1]));
        }
    }
    cout<<ans<<endl;
	return 0;
}