Building Bridge - CEOI 2017

Bridge.cpp

// Building bridges - CEOI 2017
// Complexidade O(N*sqrt(N))

#include <bits/stdc++.h>
#define inf 2000000000000000000LL
#define N 100050
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;

vector<pii> lines;

ll h[N], sum[N], n, dp[N], raiz;

struct Convex_Hull
{
    vector<pii> lines;

    double intersect(pii r, pii s)
    {
      return ((double)(r.s - s.s))/((double)(s.f - r.f));
    }

    bool bad(pii A, pii B, pii C)
    {
      return intersect(A, C) <= intersect(B, A);
    }

    void addline(pii line, bool flag)
    {
      if(flag)
      {
          while(lines.size() >= 2 && bad(lines[lines.size() - 2], lines[lines.size() - 1], line) ) lines.pop_back();

          if(lines.size() == 1 && lines[0].f == line.f) lines.pop_back();

          lines.push_back(line);
      }

      else
      {
        lines.push_back(line);

        for(int i = lines.size() - 1; i >= 0; i--)
        {
           if(i != 0 && lines[i - 1] <= lines[i]) swap(lines[i], lines[i - 1]);

           else break;
        }
      }
    }

    ll query_Hull(ll x) 
    {
        int ini = 0, fim = lines.size() - 1, mid, best = -1;

        while(fim >= ini)
        {
            mid = (ini + fim)/2;

            double pos = mid > 0? intersect(lines[mid], lines[mid - 1]) : - inf;

            if(pos <= x) best = mid, ini = mid + 1;

            else fim = mid - 1; 
        }

        return (best == -1 ? inf : lines[best].f*x + lines[best].s);
    }

} oficial, aux, pilha;

void Clear_Stack()
{
  aux.lines.clear();

  int esq = 0, dir = 0;

  while(esq < oficial.lines.size() && dir < pilha.lines.size())
  {
    if(oficial.lines[esq] >= pilha.lines[dir]) aux.addline(oficial.lines[esq], 1), esq ++;

    else aux.addline(pilha.lines[dir], 1), dir ++;
  }

  while(esq < oficial.lines.size()) aux.addline(oficial.lines[esq], 1), esq ++;

  while(dir < pilha.lines.size()) aux.addline(pilha.lines[dir], 1), dir ++;

  oficial.lines = aux.lines, pilha.lines.clear(), aux.lines.clear();
}

int main()
{
  ios::sync_with_stdio(false); cin.tie(0);

  cin>>n;

  raiz = sqrt(n);

  for(int i = 1; i <= n; i++) cin>>h[i];

  for(int i = 1; i <= n; i++) cin>>sum[i], sum[i] += sum[i - 1];

  dp[1] = 0;

  pilha.addline(pii(-2*h[1], h[1]*h[1] - sum[1]), 0);

  for(int i = 2; i <= n; i++)
  {
      ll q = oficial.query_Hull(h[i]);

      for(auto line: pilha.lines) q = min(q, line.f*h[i] + line.s);

      dp[i] = q + h[i]*h[i] + sum[i - 1];

      pilha.addline(pii(-2*h[i], h[i]*h[i] - sum[i] + dp[i]), 0);

      if(pilha.lines.size() >= raiz) Clear_Stack();
  }

  cout<<dp[n]<<"\n";
}