EducationalCF48 C - Vasya And The Mushrooms

Codeforces
問題

2行n列の畑があり、マスごとに毎秒生えるキノコ🍄の本数が決まっている
最初vasyaは1行1列にいて、キノコ🍄は畑全体に1本も生えていない
1マス移動するのには1秒かかる
全マスをちょうど1回ずつ通り、通る時にそのマスに生えているキノコ🍄を全て収穫するとき、最大で何本のキノコ🍄を収穫できるか求める

解法

各マスを一度しか通れない制約から、動きとしては
1) 下・右・上・右・下・右・上・右・...とカクカク進んでいく
2) 今いるマスから同じ行の右端まで真っ直ぐ進んでからUターンする
この2通りしかできない
1)の順番で進んでいき、各マスで「そのマスに進むまでに収穫してきた本数」と「そのマスから2)のように進んだ時に収穫できる本数」の和で答えを更新して行けばいい
後者は累積和を使えばO(1)で求められる

実装

bu[i]: 1行1列から1行m列まで進み、曲がって2行m列に行き、2行1列まで戻る という道中でi番目に通るマスまでに収穫できるキノコの本数
u[i]: ↑と同じ道中でi番目に通るマスまでの各マスの「毎秒生えるキノコの本数」の和
bd, dは2行1列から右に進んでいく場合

つまり初期位置からすぐに右に直進してUターンする場合の本数がbu[2n-1]
何回かカクカク進んでからUターンすると、カクカクしてる間に経った時間のぶん、その先の畑でbuより多くのキノコが生えてるから、それをuで調整する

#define int long long;

int n, a[2][300300], res, bu[600600], u[600600], bd[600600], d[600600];

signed main() {
	cin >> n;
	rep(i,2) rep(j,n) cin >> a[i][j];
	reps(i,1,n*2) {
		bu[i] = bu[i-1] + a[i/n][(i/n ? n-1-i%n : i%n)]*i;
		u[i] = u[i-1] + a[i/n][(i/n ? n-1-i%n : i%n)];
	}
	reps(i,0,n*2) {
		bd[i] = (i==0 ? 0 : bd[i-1]) + a[(i/n)^1][(i/n ? n-1-i%n : i%n)]*i;
		d[i] = (i==0 ? 0 : d[i-1]) + a[(i/n)^1][(i/n ? n-1-i%n : i%n)];
	}
	int b = 0;
	rep(i,n*2) {
		int r = (i%4==0 || i%4==3 ? 0 : 1), c = i/2;
		b += a[r][c] * i;
		int ic = 0;
		if (r==0) {
			ic = bu[n*2-1-c-(i%2)] - bu[c];
			ic += (u[n*2-1-c-(i%2)] - u[c]) * ((i+1)/2);
		} else {
			ic = bd[n*2-1-c-(i%2)] - bd[c];
			ic += (d[n*2-1-c-(i%2)] - d[c]) * ((i+1)/2);
		}
		chmax(res, b+ic);
	}
	cout << res << endl;
}