Submission #1265067

#TimeUsernameProblemLanguageResultExecution timeMemory
1265067escobrandBuilding Bridges (CEOI17_building)C++20
0 / 100
59 ms65396 KiB
// Li-chao Tree /* documents tài liệu của lanciu */ #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]; // Code Li-chao Tree struct Line { ll a,b; Line():a(0),b(0){} Line(ll A,ll B) : a(A),b(B){} ll cal(ll x) const {return a * x + b;} }; struct Lichao { vector<Line> t; Lichao(){} Lichao(int sz) : t(sz * 4,Line(0,LLONG_MAX)){} void up(int i,int tl,int tr,Line f) { int mid = (tl + tr)/2; if( f.cal(mid) < t[i].cal(mid) ) swap(t[i],f); if(tl == tr) return; if(f.a > t[i].a) up(i * 2,tl,mid,f); if(f.a < t[i].a) up(i * 2 + 1,mid+1,tr,f); } ll cal(int i,int tl,int tr,int pos) { if(tl > tr || tl > pos || tr < pos)return LLONG_MAX; ll ans = t[i].cal(pos); if(tl == tr)return ans; int mid = (tl + tr)/2; ans = min(ans, cal(i*2,tl,mid,pos) ); ans = min(ans, cal(i * 2 + 1,mid+1,tr,pos) ); return ans; } }; // End Code Li-chao Tree 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]; } Lichao tree(1000010); for(int i = 1;i<=n;i++) { if(i == 1) { dp[i] = 0; } else { dp[i] = tree.cal(1,1,1000000,a[i]) + a[i] * a[i] + pre[i-1]; } // Add new line for future DP queries tree.up(1,1,1000000,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...