よく考えてみると、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); }