Submission #593717

#	Time	Username	Problem	Language	Result	Execution time	Memory
593717		cadmiumsky	Building Bridges (CEOI17_building)	C++14	30 / 100	111 ms	65228 KiB

building

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const ll nmax = 1e5 + 5, hmax = 1e6 + 1, inf = 1e9 + 5;

struct func {
  ll m = inf, b = inf;
  func(ll a = inf, ll c = inf): m(a), b(c) {;} 
  ll operator()(const ll &x) const {
    return m * x + b;
  }
  bool operator == (const func& other) { return other.m == m && other.b == b; }
};

namespace LiChao {
  func aint[hmax * 4];
  void push(func x, int node = 1, int cl = 1, int cr = hmax) {
    int mid = cl + cr >> 1;
    bool md = x(mid) < aint[node](mid), rh = x(cr) < aint[node](cr);
    if(md)
      swap(aint[node], x);
    if(cl == cr || aint[node] == x)
      return;
    if(rh != md)
      push(x, 2 * node + 1, mid + 1, cr);
    else
      push(x, 2 * node, cl, mid);
    return;
  }
  ll query(int poz, int node = 1, int cl = 1, int cr = hmax) {
    if(cl == cr)
      return aint[node](poz);
    int mid = cl + cr >> 1;
    if(poz <= mid)
      return min(aint[node](poz), query(poz, 2 * node, cl, mid));
    return min(aint[node](poz), query(poz, 2 * node + 1, mid + 1, cr));
  }
};

ll h[nmax], w[nmax], dp[nmax];
ll p2(ll x) {return x * x;}


int main() {
  int n;
  cin >> n;
  for(int i = 1; i <= n; i++)
    cin >> h[i];
  for(int i = 1; i <= n; i++)
    cin >> w[i],
    w[i] += w[i - 1];
  
  dp[1] = 0;
  LiChao::push(func(-h[1] * 2, -w[1] + p2(h[1]) + dp[1]));
  
  ll rez = 0;
  for(int i = 2; i <= n; i++) {
    dp[i] = LiChao::query(h[i]) + w[i - 1] + p2(h[i]);
    //cout << dp[i] << ' ';
    LiChao::push(func(-h[i] * 2, -w[i] + p2(h[i]) + dp[i])); 
  }
  cout << dp[n] << '\n';
}

Compilation message (stderr)

building.cpp: In function 'void LiChao::push(func, int, int, int)':
building.cpp:19:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
building.cpp: In function 'll LiChao::query(int, int, int, int)':
building.cpp:34:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
building.cpp: In function 'int main()':
building.cpp:57:6: warning: unused variable 'rez' [-Wunused-variable]
   57 |   ll rez = 0;
      |      ^~~

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