Codefoces 429 D. Tricky Function
2910 단어 function
D. Tricky Function
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Iahub and Sorin are the best competitive programmers in their town. However, they can't both qualify to an important contest. The selection will be made with the help of a single problem. Blatnatalag, a friend of Iahub, managed to get hold of the problem before the contest. Because he wants to make sure Iahub will be the one qualified, he tells Iahub the following task.
You're given an (1-based) array a with n elements. Let's define function f(i, j) (1 ≤ i, j ≤ n) as (i - j)2 + g(i, j)2. Function g is calculated by the following pseudo-code:
int g(int i, int j) {
int sum = 0;
for (int k = min(i, j) + 1; k <= max(i, j); k = k + 1)
sum = sum + a[k];
return sum;
}
Find a value mini ≠ j f(i, j).
Probably by now Iahub already figured out the solution to this problem. Can you?
Input
The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 104 ≤ a[i] ≤ 104).
Output
Output a single integer — the value of mini ≠ j f(i, j).
Sample test(s)
input
4
1 0 0 -1
output
1
input
2
1 -1
output
2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int LL;
const int maxn=100100;
const LL INF=1LL<<62;
LL a[maxn];
int n;
struct POINT
{
LL x,y;
}p[maxn],temp[maxn];
bool cmpxy(POINT a,POINT b)
{
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
bool cmpy(POINT a,POINT b)
{
return a.y<b.y;
}
inline LL square(LL x)
{
return x*x;
}
LL dist(POINT a,POINT b)
{
return square(a.x-b.x)+square(a.y-b.y);
}
LL Close_pair(int left,int right)
{
LL d=INF;
if(left==right) return INF;
if(left+1==right) return dist(p[left],p[right]);
int mid=(left+right)/2;
d=min(Close_pair(left,mid),Close_pair(mid+1,right));
int k=0;
for(int i=left;i<=right;i++)
{
if(square(p[i].x-p[mid].x)<=d)
{
temp[k++]=p[i];
}
}
sort(temp,temp+k,cmpy);
for(int i=0;i<k;i++)
{
for(int j=i+1;j<k&&square(temp[i].y-temp[j].y)<d;j++)
{
d=min(d,dist(temp[i],temp[j]));
}
}
return d;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%I64d",a+i);
p[i].x=i;
p[i].y=p[i-1].y+a[i];
}
sort(p+1,p+1+n,cmpxy);
printf("%I64d
",Close_pair(1,n));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
콜백 함수를 Angular 하위 구성 요소에 전달이 예제는 구성 요소에 함수를 전달하는 것과 관련하여 최근에 직면한 문제를 다룰 것입니다. 국가 목록을 제공하는 콤보 상자 또는 테이블 구성 요소. 지금까지 모든 것이 구성 요소 자체에 캡슐화되었으며 백엔드에 대한 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.