Submission #230609

#	Time	Username	Problem	Language	Result	Execution time	Memory
230609		AlexLuchianov	Building Bridges (CEOI17_building)	C++14	100 / 100	127 ms	129144 KiB

building

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int const range = 2000000;
ll const inf = 10000000000000000LL;
ll h[1 + nmax], w[1 + nmax];

class LiChao{
private:
  struct Line{
    int a;
    ll b;
    ll eval(int x){
      return 1LL * x * a + b;
    }
  };
  vector<Line> aint;
public:
  LiChao(int n){
    aint.resize(1 + 4 * n);
  }
  void build(int node, int from, int to){
    aint[node] = {0, inf};
    if(from < to){
      int mid = (from + to) / 2;
      build(node * 2, from, mid);
      build(node * 2 + 1, mid + 1, to);
    }
  }
  void update(int node, int from, int to, Line lin){
    int mid = (from + to) / 2;

    if(lin.eval(mid) < aint[node].eval(mid))
      swap(aint[node], lin);
    if(from < to){
      if(lin.eval(from) < aint[node].eval(from))
        update(node * 2, from, mid, lin);
      else
        update(node * 2 + 1, mid + 1, to, lin);
    }
  }
  ll query(int node, int from, int to, int x){
    if(from < to){
      int mid = (from + to) / 2;
      if(x <= mid)
        return min(aint[node].eval(x), query(node * 2, from, mid, x));
      else
        return min(aint[node].eval(x), query(node * 2 + 1, mid + 1, to, x));
    } else
      return aint[node].eval(x);
  }
};
ll dp[1 + nmax];
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

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

  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> h[i];
  ll base = 0;
  for(int i = 1; i <= n; i++) {
    cin >> w[i];
    base += w[i];
    w[i] = -w[i];
  }

  LiChao cost(range);
  cost.build(1, 0, range);
  dp[1] = w[1];
  cost.update(1, 0, range, {-h[1] * 2, dp[1] + h[1] * h[1]});

  for(int i = 2;i <= n; i++){
    dp[i] = cost.query(1, 0, range, h[i]) + h[i] * h[i] + w[i];
    cost.update(1, 0, range, {-h[i] * 2, dp[i] + h[i] * h[i]});
  }

  cout << base + dp[n];
  return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:89:35: warning: narrowing conversion of '((- h[1]) * 2)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
   cost.update(1, 0, range, {-h[1] * 2, dp[1] + h[1] * h[1]});
                             ~~~~~~^~~
building.cpp:93:37: warning: narrowing conversion of '((- h[i]) * 2)' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
     cost.update(1, 0, range, {-h[i] * 2, dp[i] + h[i] * h[i]});
                               ~~~~~~^~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40