Submission #977015

#	Time	Username	Problem	Language	Result	Execution time	Memory
977015		duckindog	Building Bridges (CEOI17_building)	C++17	0 / 100	23 ms	3928 KiB

building

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n;
int h[N], w[N];
int d[N];

struct Line { 
  long long a, b;
  double x(const auto& rhs) { return 1.0 * (b - rhs.b) / (rhs.a - a); }
};
struct CHT { 
  int top;
  Line hull[N];

  void add(const Line& line) { 
    while (top >= 1 && hull[top - 1].x(hull[top]) <= hull[top - 1].x(line)) top -= 1;
    hull[++top] = line;
  }
} T;

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

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

  for (int i = 1; i <= n; ++i) d[i] = d[i - 1] + w[i];

  T.hull[0] = {-2 * h[1], 1ll * h[1] * h[1] - d[1]};

  for (int i = 2; i <= n; ++i) { 
    auto cal = [&](int it) { 
      return 1ll * h[i] * T.hull[it].a + T.hull[it].b + 1ll * h[i] * h[i] + d[i - 1];
    };    
  
    int l = 0, r = T.top - 1, it = 0;
    while (l <= r) { 
      int mid = l + r >> 1;
      if (cal(mid) >= cal(mid + 1)) l = it = mid + 1;
      else r = mid - 1;
    }

    if (i < n) T.add({-2 * h[i], cal(it) + 1ll * h[i] * h[i] - d[i]});
    else cout << cal(it) << "\n";
  }

}

Compilation message (stderr)

building.cpp:12:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 |   double x(const auto& rhs) { return 1.0 * (b - rhs.b) / (rhs.a - a); }
      |                  ^~~~
building.cpp: In function 'int32_t main()':
building.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |       int mid = l + r >> 1;
      |                 ~~^~~

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