Submission #977359

#TimeUsernameProblemLanguageResultExecution timeMemory
977359duckindogBuilding Bridges (CEOI17_building)C++17
60 / 100
67 ms9212 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; Line() : a(0), b(1'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(l - 1) > line.cal(l - 1)) f[s] = line; f[s] = line; return; } int mid = l + r >> 1; if (f[s].a > line.a) swap(f[s], line); if (f[s].cal(rrh[mid - 1]) <= line.cal(rrh[mid - 1])) insert(s << 1, l, mid, line); else { swap(f[s], line); 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; 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:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int mid = l + r >> 1;
      |             ~~^~~
building.cpp: In function 'long long int query(int, int, int, int)':
building.cpp:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int mid = l + r >> 1;
      |             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...