Submission #977368

#	Time	Username	Problem	Language	Result	Execution time	Memory
977368		duckindog	Building Bridges (CEOI17_building)	C++17	60 / 100	58 ms	9052 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;

  Line() : a(0), b(1'000'000'000'000'000'000) {}
  Line(long long a, long long b) : a(a), b(b) {}

  double x(const auto& rhs) { return 1.0 * (b - rhs.b) / (rhs.a - a); }
  long long cal(long long x) { return a * x + b; }
} f[N << 2];
vector<int> rrh;

void insert(int s, int l, int r, Line line) { 
  if (l == r) { 
    if (f[s].cal(rrh[l - 1]) > line.cal(rrh[l - 1])) f[s] = line;
    return;
  }
  int mid = l + r >> 1;
  if (f[s].cal(rrh[mid - 1]) > line.cal(rrh[mid - 1])) swap(f[s], line);
  if (f[s].a <= line.a) insert(s << 1, l, mid, line);
  else insert(s << 1 | 1, mid + 1, r, line);
}

long long query(int s, int l, int r, int i) { 
  if (i < l || i > r) return 1'000'000'000'000'000'000;
  if (l == r) return f[s].cal(rrh[i - 1]);
  int mid = l + r >> 1;
  if (i <= mid) return min(f[s].cal(rrh[i - 1]), query(s << 1, l, mid, i));
  return min(f[s].cal(rrh[i - 1]), query(s << 1 | 1, mid + 1, r, i));
}

long long dp[N];

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];

  rrh = vector<int>(h + 1, h + n + 1);
  sort(rrh.begin(), rrh.end());
  rrh.resize(unique(rrh.begin(), rrh.end()) - rrh.begin());

  insert(1, 1, rrh.size(), {-2 * h[1], 1ll * h[1] * h[1] - d[1]});
  
  for (int i = 2; i <= n; ++i) { 
    int it = lower_bound(rrh.begin(), rrh.end(), h[i]) - rrh.begin() + 1;
    dp[i] = query(1, 1, rrh.size(), it) + 1ll * h[i] * h[i] + d[i - 1];
    insert(1, 1, rrh.size(), {-2 * h[i], 1ll * h[i] * h[i] - d[i] + dp[i]});
  }

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

Compilation message (stderr)

building.cpp:16:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 |   double x(const auto& rhs) { return 1.0 * (b - rhs.b) / (rhs.a - a); }
      |                  ^~~~
building.cpp: In function 'void insert(int, int, int, Line)':
building.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int mid = l + r >> 1;
      |             ~~^~~
building.cpp: In function 'long long int query(int, int, int, int)':
building.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid = l + r >> 1;
      |             ~~^~~

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