Submission #977017

#TimeUsernameProblemLanguageResultExecution timeMemory
977017duckindogBuilding Bridges (CEOI17_building)C++17
0 / 100
24 ms3164 KiB
#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;
      |                 ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...