429D: Tricky Function

よく考えてみると、f(i,j)は二点(i,sum(1,i)a[k]),(j,sum(1,j)a[k])の距離の2乗。
ということで最近点対やって、どうぞ。

例によって無気力コーディングをしていたらマージソートで嵌ったの巻

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int x[101000];
int y[101000];
pair<int,int> p[101000];
pair<int,int> tmp[101000];
long long INF=99999999999999999LL;
long long solve(int a,int b){
	if(a>=b)return INF;
	int nx=(a+b)/2;
	long long d=min(solve(a,nx),solve(nx+1,b));
	int L=a;
	int R=nx+1;
	int at=0;
	//printf("%d, %d, %d: ",a,nx,b);
//こ↓こ↓
	while(at<b-a+1){
		if(L<=nx&&(R>b||p[L].second<p[R].second||(p[L].second==p[R].second&&p[L].first<p[R].first))){
			tmp[at++]=p[L];
		//	printf("%d(%d) ",L,p[L].second);
			L++;
		}else{
			tmp[at++]=p[R];
		//	printf("%d(%d) ",R,p[R].second);
			R++;
		}
	}//printf("\n");
//こ↑こ↑
	for(int i=0;i<at;i++)p[a+i]=tmp[i];
	vector<int> li;
	for(int i=0;i<at;i++){
		if((long long)(nx-p[a+i].first)*(nx-p[a+i].first)<=d){
			for(int j=0;j<li.size()&&(long long)(p[a+i].second-p[li[li.size()-1-j]].second)*(p[a+i].second-p[li[li.size()-1-j]].second)<=d;j++){
				d=min(d,(long long)(p[a+i].second-p[li[li.size()-1-j]].second)*(p[a+i].second-p[li[li.size()-1-j]].second)+
				(long long)(p[a+i].first-p[li[li.size()-1-j]].first)*(p[a+i].first-p[li[li.size()-1-j]].first));
			}
			li.push_back(a+i);
		}
	}
	
	return d;
}
int main(){
	int a;
	scanf("%d",&a);
	int v=0;
	for(int i=0;i<a;i++){
		int c;
		scanf("%d",&c);
		v+=c;
		x[i]=i;
		y[i]=v;
		p[i]=make_pair(x[i],y[i]);
	}
	long long ret=solve(0,a-1);
	//for(int i=0;i<a;i++)printf("%d %d\n",p[i].first,p[i].second);
	printf("%I64d\n",ret);
}