Submission #1264932

#TimeUsernameProblemLanguageResultExecution timeMemory
1264932escobrandBuilding Bridges (CEOI17_building)C++20
100 / 100
35 ms10564 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(),v.end() #define pb push_back #define ll long long #define ld long double #define fi first #define se second #define mk make_pair typedef pair<int,int> pii; const int maxn = 1e5 + 10; ll a[maxn],pre[maxn],dp[maxn]; // struct Line { ll a,b; mutable ld p; Line():a(0),b(0),p(LLONG_MIN){} Line(ll A,ll B):a(A),b(B),p(LLONG_MIN){} ll cal(ll x) const {return a * x + b;} bool operator < (const ll & x) const { return p < x;} bool operator < (const Line &o) const { if(a != o.a)return a > o.a; return b < o.b; } }; struct CHT_General : multiset<Line,less<void>> { ld xcut(iterator a,iterator b) const { return (ld)(b->b - a->b) / abs(a->a - b->a);} bool check(iterator a,iterator b) { if(b == end()) { a->p = LLONG_MAX; return 1; } if(a->a == b->a)return 0; a->p = xcut(a,b); return a->p < b->p; } void add(Line A) { iterator a = insert(A); iterator b = next(a); while(!check(a,b)) b = erase(b); if(a != begin()) { b = prev(a); if(!check(b,a)) check(b,erase(a)); } else return; while(b != begin()) { a = prev(b); if(a->p >= b->p) { check(a,erase(b)); b = a; } else break; } } ll cal(ll x) { return lower_bound(x)->cal(x);} }; // int main() { ios_base::sync_with_stdio(false); cin.tie(0); // https://oj.uz/problem/view/CEOI17_building?locale=en int n; cin>>n; for(int i = 1;i<=n;i++)cin>>a[i]; for(int i = 1;i<=n;i++) { cin>>pre[i]; pre[i] += pre[i-1]; } CHT_General container; for(int i = 1;i<=n;i++) { if(i == 1) { dp[i] = 0; } else { dp[i] = container.cal(a[i]) + a[i] * a[i] + pre[i-1]; } container.add(Line( a[i] * -2, a[i] * a[i] +dp[i] - pre[i] )); } cout<<dp[n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...