이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// G&B 7&& #&&&# J&&&&&&&J G&&&& &&& B&5 B&P J&# &&&&&& #&&&&&&&5 //
// B@# ?@@ #@&#@& Y@@57Y@@J B@@ @@7 #@P #@G Y@@ @@ J@@57J@@P //
// B@#7#&@@ &@& 5@& J@@ @@J B@@ B# @@7 #@P #@G Y@@ @@###Y 7@@ &@P //
// B@# 5@@ &@& P@& Y@@ @@J #@@ @ @@? &@P #@G 5@@ @@ ?@@ &@P //
// B@# 7@@ @@@@B P@& Y@@ @@J #@@@&&@@@ @@@&&@@G #@@&&@@@ @@&#&& 7@@ &@G //
// 7@# P@P &@? P@G &@? //
// ?# PP &7 5G &7 //
// 7 7 7 7 7 //
#include <bits/stdc++.h>
#define file "XAYCAU"
#define FastIO ios_base::sync_with_stdio(false),cin.tie(NULL)
#define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout)
#define endl " \n"
#define _ <<' '<<
#define el <<'\n'
#define f first
#define s second
#define mp make_pair
#define mp3(a,b,c) mp(a,mp(b,c))
#define pb push_back
#define eb emplace_back
#define si(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define mset(a,i) memset(a,i,sizeof a)
#define maxi(a,b) a=max(a,b)
#define mini(a,b) a=min(a,b)
#define bit(x,i) (((x)&P[i])>0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<ll,ll> pii;
typedef pair<int,pii> piii;
typedef pair<pii,pii> p4;
const int maxn=1e6+69;
const ll mod=1e9+7;
struct line{
ll a,b;
ll operator()(ll x){
return a*x+b;
}
}T[maxn*4];
int n;
ll H[maxn],W[maxn],F[maxn],sum=0;
void add(line a,int it=1,int l=0,int r=1e6){
if (r-l==1){
if (a(l)<T[it](l)) T[it]=a;
return;
}
int mid=(l+r)>>1,t=it<<1,p=it<<1|1;
if (T[it].a<a.a) swap(T[it],a);
if (T[it](mid)>a(mid)){
swap(T[it],a);
add(a,t,l,mid);
}
else add(a,p,mid,r);
}
ll get(int x,int it=1,int l=0,int r=1e6){
if (r-l==1) return T[it](x);
int mid=(l+r)>>1,t=it<<1,p=it<<1|1;
if (x<mid) return min(T[it](x),get(x,t,l,mid));
return min(T[it](x),get(x,p,mid,r));
}
int main()
{
FastIO; OpenFile;
cin>>n;
for(int i=1;i<=n;i++)
cin>>H[i];
for(int i=1;i<=n;i++){
cin>>W[i];
sum+=W[i];
}
for(int i=0;i<maxn*4;i++)
T[i]={(ll)1e9,(ll)1e18};
F[1]=-W[1];
for(int i=2;i<=n;i++){
add({-2LL*H[i-1],H[i-1]*H[i-1]+F[i-1]});
F[i]=get(H[i])+H[i]*H[i]-W[i];
}
cout<<F[n]+sum;
return 0;
}
// ▒███████▓▒░
// ███▓░░░░░░░████▓
// ░██░░░░░░░░███▓ ░▒
// ██████████████████████████ ██░░░░░░░██▓▓█████▒
// ███████░░░░░░░███░░░░░░░░░░░░░░░███▓ ▓███░░░░░████▒░░░▒████
// █████████████░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░████████▓▓██░░░███░░░░░░░░░░██░
// ▒██░░░░░░░░░░░░░░░░░░░░░░█░░░░░░░░░░░░░░░░░░░▓██████▓▓▓▓██░██▓░░░░░░░░░░░░▒█
// ░███░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██▓▓▓▓██▓███████▓████████░░░░░░█▓
// ███▓░░░░░░██░░░░░░░█░░░░░░░░░░░░░█▓░░░░░▒█▓▓▓▓▓▓██▓▓███▓▓▓█▓ ███░░░██▒
// █▓░░░░██░░░░░░░░█▓░░░░░░░░░░░░░░█▓░░░░░░███▓▓▓██▓▓▓▓▓▓▓██ ░█▓░███
// ▒█▒░░░██░░░░░░░░░██░░░░░░░░░░░░░░▓██▓░░░░░░▒█████████▓▓▓███ ▓████░
// ░█▒░░░██░░░░░░░░░░██░░░░░░░░░░░░░░████░░░░░░░░░░▒█████████░▓█ ███
// ██░░░██░░░░░░░░░░▒█▒░░░░░░░░░░░░░██░▓██░░░░░░░░░░░░░░░░█▓░░░█▓
// ▒█▒░░░█▒░░░░░░░░░░▒█▒░░░░░░░░░░░░▓██░░▒██░░░░░░░░░░░░░░░░░░░░▒█░
// ██░░░███░░░░░░░░░░██▒░░░░░░░░░░░▒██░░░░░██░░░░░░░░░░░░░░░░░░░░██
// ██░░░▒███░░░░░░░░████▓░░░░░░█░░░▒██▒░░░░░░██░░░░░░░░█▒▒██░░░░░░██▓
// ██░░░░████░░░░░░██▓ ██░░░░░██░░▒██░█▒░░░░░░██░░░░░░░██▒▒██░░░░░░██░
// ██░░░░██░▒██░░░░█▓ ▒█▒░░░███░▓█▒ ▓█░░░░░░▒█▒░░░░░░▒██░░██░░░░░░██░
// ░█▒░░░░██░░░███▒▒█▒ ▓█░░░█████░ ▓██░░░░░██░░░░░░░██░░░██░░░░░░████▒ ▓
// ██░░░░░██▒░░▓█░████ ▓█▓▒█░█▓ ░██▓░░░░██░░░░░░▓█▓░░▒██▓░░░░░░░▓██████
// ░█▒░░░░░██▓░░██ ░███ ░ ▒███░░██░░░░░░▒██░░░████▓░░░░░░▒██▓
// ███████████░▒█▒ ██ ▒████▒░░░░░▒██░░░░██▒▓██████▓
// ██░██░ ██░░░░░███░░░░▒██░░██
// ▒█▓▒█░ ▓█░░░░▒██▓░░░░░██▓░░█▒
// ██░█▓ ██ ▓▓░░░▒███▒░░░░░▒██░░█▓
// ██░▒█ ██████████████ █▒░░█████░░░░░░░██░░█▒
// ██░░██ █▓▓▓▓▓▓▓▓▓▓▓██ ░█░▓██▓██▓░░░░░░░██░░█▒
// ██░████░ ██▓▓▓▓▓▓▓▓██ █████ ░██░░░░░░░███░░█░
// ██████▓██ █▓▓▓▓▓▓██ ▓█▓░ ▒█▓░░░░░░░░██░░░█░
// ███ ██░░██░ █████ ░██░░░░░░░░░██▒░░░█░
// ██░░░░███░ ░░██▓░░░░░░░░░░██▒░░░░█░
// ██░░▓░░░███▓░ ▒███▓░░░░░░░░░░░███░░░░░░█▒
// ██████▓░░░▒████▓░ ░█▓░░░░░░░░░░██▓ ██▓░░░░▒█
// ▓██ ░████████████████▓▓░░░░░░░░░░▒██████▓▒▒▒▓██▓ ▒███▒░░██
// ▒ ▒█████░ ▓█▓▓▓▓███▓████████████░░░▒█████░░▒█▒ ▒████
// ▒▓████▓ ▒█▓▓▓▓▓▓███▓▓▓▓▓▓▓▓▓█ ▓███████
// ▓███▓▓▓▓ ░█▓▓▓▓███▓▓▓▓▓▓▓▓▓▓██ ▓▓▓▓▓████▓
// ░████░███▓▓▓█▓ ░████▓██▓██████████▓▒ ░▓▓▓▓████▓██▓
// ░███ ░█████ ██▓▓██▓▓▒███▓███▒ ███░▓▓▓▓███░▒████▒
// ▒██▒░██ ██████ ███ ▓▓ ░█████ ░████████░ ░██░▓▓█▒ ░██
//███████████████▒░░░░▒█░ ██░░░█░ ▒▓ ▓█░░░▒█░ ██░░▒▓████▓▓░ ████
// █▒░░░░░░░██▒░░░░░░░▒█░ ▒█▒░████▓▓▓▓█████████▒ ▓████▓██░ ██▓░░▓▓░░▒▓▓███░ ███░▒██
// ░██░░▒██▓░░░░░░░░░░▓██ ░██░ ░ ▒█▓▓▓▓▓▓▓▓▓▓██████████░ █▓ ██▒░░░▒▓░▒▓▓░░█████████████▓░░░░░██
// ██▓░░░░░░░░░░▒██▓ █▓ ░█░ ███████████▓▓▓▓▓███████████████▒██████░░░▓▓▓▓░░░░░░░░███▒░░░░░░░░░██
// ▓█░░░░░░░░▓██▒ ░█▓███████▓▓▓▓██████████████▓▓▓▓▓▓▓▓▓▓████▓ ▓██▓▓▓░░░░░░░░░░░░░▓██▒░░░███
// █▒░░░░░░▓██ ████▓▓▓▓▓████ ██▓▓▓▓▓▓▓█░████▓▓▓▓▓▓▓████▒ ▓▓▓▓███▒░░░░░░░░░░░▒█████▒
// █▓░░░░░██ ░███▓▓▓████▓ ██▓▓▓▓▓▓▓▓█▒ ░█████████▒ ██ ▓▓ ░▓ ███▒░░░░░░░░░███
// ██▒░░░██ █▓▓██████ ░██▓▓▓▓▓▓▓▓▓█▒ ░███████████ ░▓▓▓▓▓▓▓▒ ▒██▒░░░░░░░██
// ███░░█▓ ██▓█████████████████████████████▒ █████████ ██░░░░░░██
// ▓█████ ████████▒ ░████████ █▒░░░░██
// ░███████ ███████▒ █▒░░▓█
// ██████░ ██████ ██░▓█▒
// ▒███ ███ ████░
// ░████
컴파일 시 표준 에러 (stderr) 메시지
building.cpp: In function 'int main()':
building.cpp:12:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:66:10: note: in expansion of macro 'OpenFile'
66 | FastIO; OpenFile;
| ^~~~~~~~
building.cpp:12:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define OpenFile if(fopen(file".inp","r"))freopen(file".inp","r",stdin),freopen(file".out","w",stdout)
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:66:10: note: in expansion of macro 'OpenFile'
66 | FastIO; OpenFile;
| ^~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
