Candies

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<utility>

using namespace std;

int64_t n;

int64_t opp(int64_t k) {
  return (k+n/2)%n;
}

int main(void) {
  cin >> n;
  vector<int64_t> a(n);
  int64_t total=0;
  for(int64_t i=0;i<n;i++) {
    cin >> a[i];
    total+=a[i];
  }
  if(total%2) {
    cout << "QAQ" << endl;
    return 0;
  }
  vector<int64_t> f(n);

  int64_t foo=0;
  for(int64_t i=0;i<n/2;i++) {
    f[i]=a[i]+foo;
    foo+=a[i];
  }
  foo=0;
  for(int64_t i=n-2;i>=n/2;i--) {
    f[i]=-a[i+1]-foo;
    foo+=a[i+1];
  }

  for(int64_t i=n/2;i<n;i++) {
    f[i]+=total/2;
  }

  const int64_t INF=1000000000000000;
  int64_t m=INF;
  for(int64_t i=0;i<n;i++) {
    m=min(m,f[i]);
  }
  for(int64_t i=0;i<n;i++) {
    f[i]-=m;
  }

  /*for(int64_t i=0;i<n;i++) {
    cout << "f[" << i << "] = " << f[i] << endl;
  }
  cout << "AD" << endl;*/

  for(int64_t i=0;i<n/2;i++) {
    int64_t tmp=min(f[i],f[i+n/2]);
    f[i]-=tmp;
    f[i+n/2]-=tmp;
  }

  int64_t bar=0;
  for(int64_t i=0;i<n;i++) {
    bar+=f[i];
  }
  cout << bar << endl;

  /*for(int64_t i=0;i<n;i++) {
    cout << "f[" << i << "] = " << f[i] << endl;
  }*/

  /*const int64_t INF=1000000000000000;

  int64_t rleft=-INF;
  int64_t rright=INF;
  while(rleft != rright) {
    if(rright - rleft <= 2) break;
    int64_t r=(rright+rleft)/2;
    int64_t res1=0,res2=0;
    for(int64_t i=0;i<n;i++) {
      res1+=abs(f[i]+r);
      res2+=abs(f[i]+r+1);
    }
    cout << rleft << "," << rright << endl;
    if(res1 < res2) {
      rright=r;
    } else {
      rleft=r;
    }
  }
  int64_t res1=0,res2=0,res3=0,res4=0;
  for(int64_t i=0;i<n;i++) {
    res1+=abs(f[i]+rleft);
    res2+=abs(f[i]+rleft+1);
    res3+=abs(f[i]+rleft+2);
    res4+=abs(f[i]+rleft+3);
  }
  cout << min(res1,min(res2,min(res3,res4))) << endl;*/

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED