AGC027 B - Garbage Collector

問題

https://beta.atcoder.jp/contests/agc027/tasks/agc027_b

考察

移動コストが\((k+1)^2\)なのが特徴的。
\((k+1)^2=1+3+5+\cdots+2k+1\)と変形してみる。
すると最初のごみがコスト5、次もコスト5、次は7、9、11、…
各ゴミについてそれをコストいくつで運ぶかは、何回捨てるかを決めると愚直にできる
あとは累積和を使って高速に計算
(long longでオーバーする場合があるのでそういう場合は排除しないとWA、なにそれ)

コード

#include <bits/stdc++.h>
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
using namespace std;

int f(int k){
	if(k==0) return 5;
	else if(k==1) return 0;
	else return 2;
}

ll x[200001], x2[200001];

int main(){
	int n,X; cin>>n>>X;
	FOR(i,0,n) cin>>x[i];
	x2[0]=x[0];
	FOR(i,1,n) x2[i]=x2[i-1]+x[i];

	ll m=1e18;
	FOR(k,1,n+1){
		int t=0;
		ll ans=0;
		while(n-1-t*k>=0){
			ans+=f(t)*x2[n-1-t*k];
			if(ans>m) break;
			t++;
		}
		if(ans>m) continue;
		ans+=(ll)X*(n+k);
		m=min(ans,m);
	}
	cout<<m<<endl;
}