fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <stdlib.h>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 1e5 + 5;
  8. typedef long long ll;
  9.  
  10. struct pii{ int x, y; };
  11.  
  12. int A[MAXN], N, pre[MAXN];
  13.  
  14. ll sq(ll x){ return x * x; }
  15. bool comp1(pii a, pii b){ return a.x < b.x; }
  16. bool comp2(pii a, pii b){ return a.y < b.y; }
  17. ll dist(pii a, pii b){ return sq(a.x - b.x) + sq(a.y - b.y); }
  18.  
  19. int brute(pii S[], int N){
  20.   ll cd = 10000000000000000LL;
  21.   for(int i=0; i<N; ++i)
  22.     for(int j=i+1; j<N; ++j) cd = min(cd, dist(S[i], S[j]));
  23.   return cd;
  24. }
  25.  
  26. int unite(pii S[], int size, ll cd){
  27.   for(int i=0; i<size; ++i)
  28.     for(int j=i+1; j<min(size, i+8); ++j)
  29.       cd = min(cd, dist(S[i], S[j]));
  30.   return cd;
  31. }
  32.  
  33. int divide(pii Px[], pii Py[], int N){
  34.   if(N <= 3) return brute(Px, N);
  35.   int mid = N / 2, l = 0, r = 0, j = 0;
  36.   pii Pyl[mid + 1], Pyr[N - mid], mp = Px[mid];
  37.   for(int i=0; i<N; ++i){
  38.     if(Py[i].x <= mp.x) Pyl[l++] = Py[i];
  39.     else Pyr[r++] = Py[i];
  40.   }
  41.   ll d = min(divide(Px, Pyl, mid), divide(Px + mid, Pyr, N - mid));
  42.   pii S[N + 1];
  43.   for(int i=0; i<N; ++i)
  44.     if(abs(Py[i].x - mp.x) < d) S[j++] = Py[i];
  45.   return min(d, 1LL * unite(S, j, d));
  46. }
  47.  
  48. int main(){
  49.   scanf("%d", &N);
  50.   for(int i=1; i<=N; ++i){
  51.     scanf("%d", &A[i]);
  52.     pre[i] += pre[i - 1] + A[i];
  53.   }
  54.   pii Px[N + 1], Py[N + 1];
  55.   for(int i=0; i<N; ++i) Px[i] = (pii){i + 1, pre[i + 1]}, Py[i] = (pii){i + 1, pre[i + 1]};
  56.   sort(Px, Px + N, comp1); sort(Py, Py + N, comp2);
  57.   printf("%d\n", divide(Px, Py, N));
  58.   return 0;
  59. }
Success #stdin #stdout 0s 4256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1874919424
https://ideone.com/hksrSH
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!