Submission #919687

#TimeUsernameProblemLanguageResultExecution timeMemory
919687penguin133Building Bridges (CEOI17_building)C++17
100 / 100
40 ms10576 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, H[100005], W[100005]; struct Line { mutable int k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(int x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { // for doubles, use inf = 1/.0, div(a,b) = a / b static const int inf = 5e18;// implement this int div(int a, int b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(int k, int m) { // insert y = kx + m auto z = insert({k, m, 0}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } int query(int x) { // max query assert(!empty()); auto l = *lower_bound(x); return l.k * x + l.m; } }; int dp[100005], P[100005]; void solve(){ cin >> n; for(int i = 1; i <= n; i++)cin >> H[i]; for(int i = 1; i <= n; i++)cin >> W[i], P[i] = P[i - 1] + W[i]; dp[1] = 0; LineContainer hull; hull.add(2 * H[1], -(H[1] * H[1] - P[1])); for(int i = 2; i <= n; i++){ dp[i] = -hull.query(H[i]) + H[i] * H[i] + P[i - 1]; hull.add(2 * H[i], -(H[i] * H[i] - P[i] + dp[i])); } cout << dp[n]; } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

Compilation message (stderr)

building.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...