Codeforces 429(#245 Div1) D. Tricky Function

問題

a[i]が与えられる。
(i - j)^2 + (Σ[k=j,i]a[k]) ^ 2の最小値を求めよ。

制約条件

a[i]の要素≦10^5
|a[i]|≦10^4

方針

n個の点で、i番目の点の座標が(i, Σa[i])であるようなものを考えると、
与えられた問題は、最近点対の距離を求める問題。

最近点対を使ってもよいし、この問題の場合なんか適当に2秒間一杯ループをまわしても通ってしまう。

ソースコード

int n;
ll s[100000];

int main(){
	double start = getnow();
	
	int cnt = 0;
	ll ans = 1e18;
	
	rep(w, n - 1) rep(i, n - w - 1){
		ans = min(ans, (w + 1ll) * (w + 1ll) + (s[i + w + 1] - s[i]) * (s[i + w + 1] - s[i]));
		
		if(++cnt % 131072 == 0 && getnow() - start > 1.9){
			w = n;
			break;
		}
	}
	cout << ans << endl;
	
	return 0;
}