【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;

}

巴特西

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

最新文章

热门文章